UOJ499 喂鸽子

Description

题面挺长挂个链接

Solution

「所有的鸽子都饱了」本质就是求每个鸽子第一次饱的时刻的最大值嘛，由于第一次本应是「最小」的含义，所以最值反演一手。

$\max\{S\} = \min_{T\subseteq S \cap T\ne \emptyset}(-1)^{|T|+1}\min\{T\}$

由于鸽子之间并没区别，所以枚举集合可以简化为枚举集合大小。
设 f[i] 表示在 $n$ 只鸽子中任意喂，一个大小为 $i$ 的鸽子集合里存在一只被喂饱的期望时刻。则：

$\max\{S\} = \sum_{i=1}^{n}(-1)^{i}\binom{n}{i}f_i$

求期望常用方法是差分成求概率。设 p[c][j] 表示在 $n$ 只鸽子中任意喂，一个大小为 $c$ 的鸽子集合在第 $j$ 个时刻仍未有鸽子被喂饱的概率。则有

$f_c = \sum_{j\ge 0}p_{c,j}$

我们可以枚举喂了多少次鸽子集合里的鸽子来。设 g[c][j] 表示在大小为 $c$ 的鸽子集合里喂了 $j$ 次仍未有鸽子饱的概率，那么可以得到：

$p_{c,j} = \sum_{i=0}^{j}\binom{j}{i}g_{c,i}(\frac{c}{n})^i(\frac{n-c}n)^{j-i}$

把这个式子带入上式可以得到

$\begin{aligned} f_c &= \sum_{j\ge 0}\sum_{i=0}^{j}g_{c,i}(\frac{c}{n})^i(\frac{n-c}n)^{j-i}\\ &=\sum_{i\ge 0}g_{c,i}(\frac{c}{n})^i\sum_{j\ge 0}\binom{j}{i}(\frac{n-c}{n})^{j-i}\\ &=\sum_{i\ge 0}g_{c,i}(\frac{c}{n})^i\sum_{j\ge 0}\binom{i+j}{j}(\frac{n-c}{n})^{j} \end{aligned}$

后面的式子怎么求和呢？有一个广义二项式定理的小结论：

$\begin{aligned} (\frac{1}{1-x})^{j+1}&=(1-x)^{-j-1}\\ &=\sum_{i=0}^{\infin}(-x)^{i}\frac{(-j-1)(-j-2)\cdots(-j-i)}{i!}\\ &=\sum_{i=0}^{\infin}x^i\frac{(j+1)(j+2)\cdots (j+i)}{i!} \\ &=\sum_{i=0}^{\infin}x^i\binom{j+i}{i} \end{aligned}$

所以 f[c] 的求解可以简化为

$\begin{aligned} f_c &= \sum_{i\ge 0}g_{c,i}(\frac{c}{n})^i\sum_{j\ge 0}\binom{i+j}{j}(\frac{n-c}{n})^{j} \\ &=\sum_{i\ge 0}g_{c,i}(\frac{c}{n})^i(\frac{n}{c})^{i+1}\\ &=\frac{n}{c}\sum_{i\ge 0}g_{c,i} \end{aligned}$

$i$ 的上限显然是 $c\times (k-1)$。也就是在求出来 g[][] 后求 f[] 是 $\mathcal{O}(n^2k)$ 的。

求 g[c][i] 需要我们转化一下思路。显然 g[c][i] 乘上 $c^i$ 就是方案数。我们设方案数为 h[c][i] 。那么 h[c][i] 其实是很好递推的。

$h_{c,i}=c\times (h_{c,i-1}-\binom{i-1}{k-1}h_{c-1,i-k})$

因为 h[c][i] 的方案一定是由 h[c][i-1] 的方案，再任意喂一只鸽子得到的，并且至多在喂第 $i$ 次的时候多出一只喂饱的鸽子。所以我们可以钦定是谁喂饱了，减去这部分方案即可。

注意：推式子的时候不仅要注意该方案是从哪部分方案来的，而且要注意是怎么来的。比如在这里是由任意喂一只鸽子得来的，所以我们需要乘上系数 $c$ 。

h[][] 和 f[] 都是可以在 $\mathcal{O}(n^2k)$ 的时间内递推出来的。于是做完了。

Code

const int N = 55, L = 5e4 + 5, mod = 998244353;
using namespace std;
int n, k;
int h[N][L], fac[L], inv[L], invf[L]; 
long long f[N];
int binom(int n, int m){
    if(n < 0 or m < 0 or n - m < 0) return 0;
    return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
void Prework(int n, int k){
    fac[0] = inv[0] = invf[0] = fac[1] = inv[1] = invf[1] = 1;
    int up = n * k;
    for(int i = 2; i <= up; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod; 
    for(int i = 0; i <= up; ++i) h[0][i] = 1;
    for(int i = 0; i <= n; ++i)  h[i][0] = 1;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i * (k - 1); ++j){
        h[i][j] = h[i][j - 1];
        if(j - k >= 0)
            h[i][j] -= 1ll * binom(j - 1, k - 1) * h[i - 1][j - k] % mod;
        h[i][j] = (1ll * h[i][j] * i % mod + mod) % mod;
    }
    for(int i = 1; i <= n; ++i)
    for(int j = 1, d = inv[i]; j <= up; ++j, d = 1ll * d * inv[i] % mod)
        h[i][j] = 1ll * h[i][j] * d % mod;
    for(int i = 1; i <= n; ++i)
    for(int j = 0; j <= up; ++j)
        f[i] += h[i][j];
    for(int i = 1; i <= n; ++i)
        f[i] = 1ll * f[i] * n % mod * inv[i] % mod;
}
int main(){

    r(n, k);
    Prework(n, k);
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
        if(i & 1) ans += 1ll * binom(n, i) * f[i] % mod;
        else ans -= 1ll * binom(n, i) * f[i] % mod;
    ans = (ans % mod + mod) % mod;
    w(ans);