HDU 4624 期望

一行 $ N $ 个白色的球,每次等概率随机一个区间 $ [L,R] $ 将这些染黑。问期望多少次染黑所有球。

Sol.

@CLJ 的题。计数问题选讲的课件里有。

可知题目所求为 $ \mathbb{E}[\max_{i=1}^nX_i] $ ,其中 $ X_i $ 表示这个位置被染黑的时间,由期望的线性性和 maximum-minimums identity 有

$$ \mathbb E[\max_{i=1}^n X_i]=\sum_{S\sub[n]}(-1)^{|S|-1} \mathbb{E}[\min_{i\in S}X_i] $$

问题变为怎么求 $ \mathbb E[\min_{i\in S} X_i] $ ,这表示第一次染到 $ S $ 这个集合的期望时间,其等于 $ {{n+1\choose2}\over A} $ ,其中 $ A $ 为覆盖 $ S $ 中至少一个点的区间个数。

考虑递推算这个东西。 $ f_{i,s,b} $ 表示考虑前 $ i $ 个白球,黑球(未覆盖)区间数为 $ s $ 且黑球的奇偶性为 $ b $ (容斥用)的的时间,则有

$$ f_{i,s,b}=\sum_{j}f_{j,s-{i-j\choose2},b\oplus1} $$

那么 $ \mathbb{E}[\max_{i=1}^n X_i]={n+1\choose2}\sum_{i}{f_{i,t,1}-f_{i,t,0}\over{n+1\choose2}-t-{n-i+1\choose2}} $ .

原题要高精度小数……懒得写了……

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
#define G(n) (((n) * (n + 1)) >> 1)
long long f[55][2555][2];
int main()
{
    int t; read(t);
    while(t--)
    {
        int n; read(n);
        memset(f, 0, sizeof f);
        f[0][0][0] = 1;
        for(int i = 1; i <= n; ++i) for(int j = 0; j < i; ++j) for(int s = G(i - j - 1); s <= G(i); ++s)
            f[i][s][0] += f[j][s - G(i - j - 1)][1], f[i][s][1] += f[j][s - G(i - j - 1)][0];
        long double ans = 0, tot = G(n);
        for(int i = 1; i <= n; ++i) for(int s = 0; s <= G(i); ++s) if(f[i][s][1] - f[i][s][0] != 0)
            ans += tot * (f[i][s][1] - f[i][s][0]) / (tot - s - G(n - i));
        printf("%.15Lf\n", ans);
    }
    return 0;
}

Codeforces #463 Sol.

A

给一个串 $ s (|s|\le1000) $,找出任意一个回文串 $ S(|S|\le10000) $ ,使得 $ s $ 是 $ S $ 的子序列。

Sol.

直接输出 $ s+rev(s) $.

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
char s[maxn];
int main()
{
    scanf("%s", &s);
    int len = strlen(s);
    for(int i = 0; i < len; ++i) putchar(s[i]);
    for(int i = len - 1; ~i; --i) putchar(s[i]);
    return 0;
}

B

$ f(n) $ 为非零的数位之积,

img

求 $g(i)=k,i\in[l,r] $ 的个数。

范围 $ Q \le 2\times10^5,1\le l\le r \le10^6,1\le k\le9 $.

Sol.

打 $ f,g,h(l,k):=\sum_{i\le l} [g(i)=k] $ 的表.

注意数位积与数位和不一样。比赛时我以为 $ g $ 对 $ f $ 满足结合律,实际上是分配律(把数拆成数位之间连接的是加法)。数位和的性质过于良好,等价于在 $ \mod 9 $ 意义下的值,以至于我想当然了。被卡了很久。

要多长点心眼,遇到这种题要把“理所当然”的结论再验证一遍。不过也暴露出我找反例的能力有点弱,应该找最可能出现反例的地方想的。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e6 + 10;
int g[maxn], cnt[maxn][10], prod[maxn];
int main()
{
    memset(cnt, 0, sizeof cnt);memset(g, 0, sizeof g);
    for(int i = 1; i < 10; ++i) 
    {
        memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
        g[i] = prod[i] = i;
        cnt[i][g[i]] ++;
    }
    for(int i = 10; i < maxn; ++i)
    {
        memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
        g[i] = g[prod[i] = prod[i / 10] * (i % 10 == 0 ? 1 : i % 10)];
        cnt[i][g[i]]++;
    }
    int q; read(q);
    while(q--)
    {
        int l, r, k; read(l, r, k);
        printf("%d\n", cnt[r][k] - cnt[l - 1][k]);
    }
    return 0;
}

C

找出 $ P $ 的一个排列,定义img , $ g(i):=\min\{j:f(i,j)=i\} $.

给定 $ N\le10^6,A,B $ ,使得对所有 $ i\in[1,n],~g(i)=A\text{ or } B $.

Sol.

容易看出这是将一个排列分解为长度为 $ A $ 或 $ B $ 的置换。

解同余方程或者暴力枚出这俩的系数,然后循环移位一下即是合法构造。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
    int n, a, b; read(n, a, b);
    int ti = -1;
    for(int i = 0; i <= n / a; ++i)
    {
        if((n - i * a) % b == 0)
        {
            ti = i;
            break;
        }
    }
    if(ti == -1) {puts("-1"); return 0;}
    int tj = (n - ti * a) / b;
    for(int i = 0; i < ti; ++i) for(int j = 1; j <= a; ++j)
        printf("%d ", i * a + (j) % a + 1);
    for(int i = 0; i < tj; ++i) for(int j = 1; j <= b; ++j)
        printf("%d ", ti * a + i * b + (j) % b + 1);
    return 0;
}

D

初始给一个点 $ 1 $ ,权值为 $ 0 $ 。有两种操作,

  1. 在 $ p $ 下面接一个下一个编号的点,权值为 $ q $.
  2. 询问 $ p $ 的祖先序列中的最长不降权值且和不超过 $ q $ 的长度最长长度。

询问 $ \le 4\times 10 ^5 $, 权值 $ \le 10^{18} $.

Sol.

建一棵按题意形态的原树,一棵新树。原数维护倍增表,找出第一个大于当结点权值的祖先,返回作为其新树的父亲。在新树上同样维护倍增表,询问时二分即可。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 4e5 + 100;
long long ww[maxn];
namespace T1
{
long long w[maxn][20]; int fa[maxn][20];
int check(int u, long long v)
{
    for(int i = 19; ~i; --i) if(w[u][i] < v) u = fa[u][i];
    if(ww[u] >= v) return u; else return fa[u][0];
}
void add(int u, int f)
{
    fa[u][0] = f, w[u][0] = ww[u];
    for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = max(w[fa[u][i - 1]][i - 1], w[u][i - 1]);
}
}
namespace T2
{
int fa[maxn][20], dep[maxn];
long long w[maxn][20];
inline void add(int u, int f)
{
    fa[u][0] = f, w[u][0] = ww[u];
    dep[u] = dep[f] + 1;
    for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = w[u][i - 1] + w[fa[u][i - 1]][i - 1];
}
int check(int u, long long x)
{
    int du = dep[u];
    for(int i = 19; ~i; --i) if(w[u][i] <= x) x -= w[u][i], u = fa[u][i];
    return du - dep[u];
}
}
//long long
int main()
{
    T2::dep[1] = 1;
    int q; read(q);
    long long last = 0, cnt = 1;
    while(q--)
    {
        long long t, p, q; read(t, p, q);  p ^= last, q ^= last;
        if(t == 1)
        {
            ww[++cnt] = q;
            int ti = T1::check(p, ww[cnt]);
            T1::add(cnt, p);
            T2::add(cnt, ti);
        }
        else
        {
            printf("%d\n", last = T2::check(p, q));
        }
    }
    return 0;
}

E

给出 $ n \le 10^9, k\le 5000 $ ,求 $ \sum {n \choose i} i ^k $.

Sol. 1

我们注意到和这个形式相像的式子即为二项式展开 $ (1+x)^n=\sum {n \choose i} x^i $。

这启发我们一定可以从这个式子变形得到原式,我们考虑求导补次,即 $ x[(1+x)^n]' = \sum {n \choose i} ix^{i} $。

发现如此操作 $ k $ 次后得到的式子令 $ x=1 $ 即为我们需要的答案。

我们有 $ x {\mathrm{d}\over\mathrm{d}x} (x^a(1+x)^b) = ax^a(1+x)^b+bx^{a+1}(1+x)^{b-1} $ ,写出递推方程,$ f_{k,a,b} = af_{k-1,a,b}+bf_{k-1,a+1,b-1} $ ,记忆化搜索一遍可得答案,注意判断 $ a,b $ 为 $0 $ 的情况。

这个虽然看起来时是三维的,但注意到后两维和为定值,这降了一维。

Sol. 2

继续沿用求导的思路,但我们不补次,于是得到 $ [(1+x)^n]^{(k)} = n^{\underline k}(1+x)^{n-k}=\sum{n \choose i} i^{\underline k}x^{i-k} $.

一个自然而然的想法是使用第二类把幂表示成下降幂,即 $ \sum \left\{ \begin{matrix} n \\ k\end{matrix} \right\} x^{\underline k} = x^n $.

从而 $ \sum_i {n \choose i} i^k = \sum_i{n \choose i}\sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} i^{\underline j} = \sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} \sum_i {n \choose i}i^{\underline j} = \sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} [n^{\underline j}(1+x)^{n-j}]_{x=1} $.

第二类可以 $ O(k^2) $ 预处理,下降幂 $ O(k) $ 预处理,$ 2 $ 的幂 $ O(\lg n) $ 直接计算。总的复杂度仍然是 $ O(k^2) $.

同样注意 $ n-j $ 小于等于 $ 0 $ 的情况。

Code 1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5000 + 10, mod = 1e9 + 7;
long long power(long long a, long long b)
{
    long long ret = 1;
    for(; b; b >>= 1, (a *= a) %= mod) if(b & 1)
        (ret *= a) %= mod;
    return ret;
}
long long dp[maxn][maxn];
long long cal(int k, int a, int n)
{
    if(~dp[k][a]) return dp[k][a];
    if(k == 0) return dp[k][a] = power(2, n - a);
    int b = n - a;
    return dp[k][a] = ((a ? 1ll * (a) % mod * cal(k - 1, a, n) % mod : 0) + (b ? 1ll * (b) % mod * cal(k - 1, a + 1, n) % mod : 0)) % mod;
}
int main()
{
    int n, k; read(n, k);
    memset(dp, -1, sizeof dp);
    printf("%d\n", cal(k, 0, n));
}

Code 2

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int mod = 1e9 + 7, maxn = 5000 + 5;
long long power(long long a,long long b){long long ret = 1;for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod; return ret;}
long long S[maxn][maxn], D[maxn];
int main()
{
    int n, k; read(n, k);
    S[0][0] = 1;
    for(int i = 1; i <= k; ++i) for(int j = 1; j <= i; ++j)
        S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j] % mod) % mod;
    D[0] = n;
    for(int i = 1; i <= k; ++i) D[i] = (n - i) * D[i - 1] % mod;
    int ret = 0;
    for(int i = 1; i <= min(n, k); ++i)
        (ret += S[k][i] * D[i - 1] % mod * power(2, n - i) % mod) %= mod;
    printf("%d\n", ret);
    return 0;
}

BZOJ 4833 反演

已知 $ f(n)=2f(n-1)+f(n-2), f(0)=0,f(1)=1,g(n):=\text{lcm}\{f(1),f(2),\cdots,f(n)\} $ ,求

$$ \sum_{i=1}^nig(i) \mod p $$

Sol.

大致思路同 51nod 1223.

注意到 $ \gcd(f(n),f(m))=f(\gcd(n,m)) $ ,带入熟知结论得 $ g(n)=\prod_{T\sub[n]} f(\gcd_{i\in T}(i))^{(-1)^{|T|+1}} $ .

令 $ f(n)=\prod_{d|n} h(d) $ ,带入得

$$ \begin{align} g(n) &= \prod_{T\sub[n]}\left(\prod_{d|\gcd_{i\in T}(i)} h(d) \right)^{(-1)^{|T|+1}} \\ &= \prod_{d=1}^n h(d)^{\sum_{T\sub [\lfloor n/d \rfloor]}(-1)^{|T|+1}} \\ &= \prod_{d=1}^n h(d) \end{align} $$

求出 $ h $ 后问题是平凡的.

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const long long maxn = 5e6;
long long f[maxn], g[maxn];
inline long long power(long long a,long long b,long long p){long long ret=1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)ret=1ll*ret*a%p;return ret;}
int main()
{
    long long t; read(t);
    f[0] = 0, f[1] = 1;
    while(t--)
    {
        long long n; long long p; read(n, p);
        for(int i = 2; i <= n; ++i) f[i] = (2 * f[i - 1] + f[i - 2]) % p;
        for(int i = 1; i <= n; ++i) g[i] = f[i];
        for(int i = 1; i <= n; ++i)
        {
            long long inv = power(g[i], p - 2, p);
            for(int j = i + i; j <= n; j += i) g[j] = 1ll * g[j] * inv % p;
        }
        long long lcm = 1, ans = 0;
        for(int i = 1; i <= n; ++i) lcm = 1ll * lcm * g[i] % p, (ans += 1ll * lcm * i % p) %= p;
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ 4762 容斥 DP

定义一个非空集合是合法的,当且仅当它满足以下两个条件。

  1. 集合内所有元素and和为0;
  2. 它的非空子集中仅有它本身满足1.

给出一个集合S,求它的合法非空子集数。

$ |S|\le 1000, a_i<1024 $ .

Sol.

很棒的容斥题.

$ S $ 的 AND 和合法, iff 任意 $ |S-1| $ 大小的子集的 AND 和不为零.

定义 $ S_a:=S-\{a\}, f(S):=\&_{i\in S} i $ .

题目等价求

$$ \begin{align} \sum_S[f(S)=0 \and \bigwedge_{a\in S} (f(S_a)\neq0)] = \sum_S[f(S)=0][\bigwedge_{a\in S}(f(S_a)\neq 0)] \end{align} $$

对后项考虑运用 De Morgan 后容斥,有

$$ [\bigwedge_{a\in S} (f(S_a)\neq 0)] = \sum_{S' \sub S} [\bigwedge_{a\in S'} (f(S_a)=0)](-1)^{|S'|} $$

注意到 $ [\bigwedge_{a\in S'}(f(S_a)=0)] = [\bigvee_{a\in S'} f(S_a)=0] $ ,代入原式

$$ \sum_S\sum_{S'\sub S}[f(S)=0][\bigvee_{a\in S'}f(S_a) = 0](-1)^{|S'|} $$

现在可以很方便的设计状态啦~

设 $ f_{i,k,j} := $ 前 $ i $ 个元素前项值为 $ k $ 后项值为 $ j $ 的方案数,初值 $ f_{0,1023,1023}=1 $ ,答案为 $ f_{n,0,0} $ .

分别考虑不加入 $ S $ ;加入 $ S $ 但不加入 $ S' $ ;加入 $ S' $ . 转移如下

$$ \begin{align} f_{i+1,k,j} &\leftarrow f_{i,k,j} \\ f_{i+1,k,j\&d} &\leftarrow f_{i,k,j} \\ f_{i+1,k\&d,k|j\&d} &\leftarrow -f_{i,k,j} \end{align} $$

枚举子集即可.

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1030, mod = 1e9 + 7;
int f[2][maxn][maxn];
int main()
{
    int n; read(n);
    f[0][1023][1023] = 1;
    for(int i = 1, d; i <= n; ++i)
    {
        read(d);
        for(int j = 0; j < 1024; f[i & 1][0][j] = 0, ++j) for(int k = j; k; k = (k - 1) & j)
            f[i & 1][k][j] = 0;
        for(int j = 0; j < 1024; ++j) 
        {
            for(int k = j; k; k = (k - 1) & j) if(f[i & 1 ^ 1][k][j])
                (f[i & 1][k][j] += f[i & 1 ^ 1][k][j]) %= mod, (f[i & 1][k & d][j & d] += f[i & 1 ^ 1][k][j]) %= mod, (f[i & 1][k & d][k | j & d] += (mod - f[i & 1 ^ 1][k][j])) %= mod;
            (f[i & 1][0][j] += f[i & 1 ^ 1][0][j]) %= mod, (f[i & 1][0][j & d] += f[i & 1 ^ 1][0][j]) %= mod, (f[i & 1][0][j & d] += (mod - f[i & 1 ^ 1][0][j])) %= mod;
        }
    }
    printf("%d\n", f[n & 1][0][0]);
    return 0;
}

BZOJ 4001 生成函数 概率

求 $ n $ 点二叉树的叶子树期望.

Sol.

设 $ g_n:= n $ 点二叉树形态总数,$ f_n:=n $ 点二叉树叶子的期望数.

有 $ g_n=\sum_ig_ig_{n-1-i},g_0=1, f_n=\sum_i(f_i+f_{n-1-i}){g_ig_{n-1-i}\over g_n}, f_0=1,f_1=1 $ .

求 $g$ 的 OGF $ G $ 有 $ G={1-\sqrt{1-4x}\over 2x} $ .

对 $ f $ 由对称性,移项有 $ f_ng_n=2\sum_if_ig_ig_{n-1-i} $ ,记 $ h_n=f_ng_n $ ,求 $ h $ 的 OGF 有 $ H = 2xHG+x $ 即 $ H=x(1-4x)^{-{1\over2}} $ .

用广义二项式定理展开得 $ [x^{n+1}]H={2n\choose n} $ ,即 $ [x^n]H=h_n={2n-2\choose n-1} $.

同理有 $ [x^n]G=g_n={(2n)!\over(n+1)!n!} $ .

最后 $ f_n={h_n\over g_n}={n(n+1)\over 2(2n-1)} $ .

Code

#include <bits/stdc++.h>
int main()
{
    double n; scanf("%lf", &n);
    printf("%.9lf\n", n * (n + 1) / 2 / (2 * n - 1));
    return 0;
}