【集训队作业2018】喂鸽子

题面

题解

列出 min-max 容斥的式子：

[E(max(S)) = sum_{T subseteq S} (-1) ^ {|T| + 1} E(min(T)) ]

这道题是要求一只鸽子被喂饱的时间最大值的期望，于是套下这个式子。

设 (max_i) 表示鸽子数为 (i) 时被喂饱的时间最大值的期望，(min_i) 表示鸽子数为 (i) 时被喂饱的时间最小值的期望，那么有：

[mathrm{max}_n = sum_{i = 1}^n (-1) ^ {i + 1} inom ni mathrm{min}_i ]

考虑如何求出 (min_n)。设 (p_{c, i}) 表示在 (n) 只鸽子中选出 (c) 只鸽子，时间为 (i) 时有喂饱的概率，则 (min_c = sum_{i geq 1} i p_{c, i})。

想到一个经典的转化：设 (p'_{c, i}) 表示时间 $ > i$ 时的概率，则 (min_c = sum_{i geq 0} p'_{c, i})。

设 (g_{c, s}) 表示 (c) 只鸽子中，时间为 (s) 时还没有一只鸽子饱了的概率。

那么有：

[mathrm {min}_c =sum_{i geq 0} sum_{s = 0}^i inom is g_{c, s} left( frac {n - c} n ight) ^ {i - s} left( frac cn ight)^s ]

将 (i gets i - s)，则有：

[mathrm{min}_c = sum_{s geq 0} g_{c, s} left( frac cn ight) ^ s sum_{i geq 0} inom {i + s} s left( frac {n - c}n ight) ^ i ]

显然 (s leq c(k - 1))，同时令 (x = dfrac {n - c} n)，那么后面那个式子就是 (left(dfrac 1 {1 - x} ight) ^ {s + 1} = left( dfrac nc ight) ^ {s + 1})。

再化简，可以得到：

[mathrm{min}_c = frac nc sum_{s = 0} ^ {c(k - 1)} g_{c, s} ]

感觉概率好像很难算的亚子，于是考虑求出方案数 (f_{c, s} = c^s g_{c, s})。

因为鸽子之间有顺序，所以可以得出 (f_{c, s}) 的指数型生成函数 (F_c(x))。设 (f(x) = sum_{0 leq i < k} frac {x^i}{i!})，有

[F_c(x) = f^c(x) = left( sum_{0 leq i < k} frac {x ^ i} {i!} ight) ^ c ]

直接 NTT 可以做到 (mathcal O(n^2k log))，但是可以通过一些方法做到更优。

因为 (f(x) = sum_{0 leq i < k} frac {x^i}{i!})，所以 (f'(x) = sum_{0 leq i < k - 1} frac {x^i}{i!} = f(x) - frac {x ^ {k - 1}}{(k - 1)!})。

设 (f'_{c, s} = [x^s] F'_c(x))，于是：

[egin{aligned} left[f^c(x) ight]' &= cf^{c - 1}(x) f'(x) \ &= cf^{c - 1}(x)left(f(x) - frac {x ^ {k - 1}}{(k - 1)!} ight) \ &= cleft[f^c(x) - frac {x ^ {k - 1}}{(k - 1)!} f^{c - 1}(x) ight] end{aligned} ]

即：

[f'_{c, s} = c left( f_{c, s} - frac 1 {(k - 1)!} f_{c - 1, s - k + 1} ight) ]

积分回来就是：

[f_{c, s + 1} = frac c{s + 1} left( f_{c, s} - frac 1{(k - 1)!} f_{c - 1, s - k + 1} ight) ]

这样子就可以做到 (mathcal O(n^2k)) 了。

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

const int N(55), M(1010 * N), Mod(998244353);
int n, m, K, ans, f[N][M], fac[M], inv[M];

int C(int n, int m) { return 1ll * fac[n] * inv[m] % Mod * inv[n - m] % Mod; }
int fastpow(int x, int y)
{
	int ans = 1;
	for (; y; y >>= 1, x = 1ll * x * x % Mod)
		if (y & 1) ans = 1ll * ans * x % Mod;
	return ans;
}

int main()
{
	std::scanf("%d%d", &n, &K), m = n * K, fac[0] = inv[0] = 1;
	for (int i = 1; i <= m; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
	inv[m] = fastpow(fac[m], Mod - 2);
	for (int i = m - 1; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;
	for (int i = 0; i <= n; i++) f[i][0] = 1;
	for (int i = 0; i < K; i++) f[1][i] = inv[i];
	for (int i = 2; i <= n; i++)
		for (int j = 0; j < i * (K - 1); j++)
		{
			f[i][j + 1] = 1ll * i * fac[j] % Mod * inv[j + 1] % Mod;
			f[i][j + 1] = 1ll * f[i][j + 1] * (f[i][j] + Mod - ((j >= K - 1) ? 1ll * inv[K - 1] * f[i - 1][j - K + 1] % Mod : 0ll)) % Mod;
		}
	for (int i = 1; i <= n; i++)
	{
		int res = 0, p = 1ll * inv[i] * fac[i - 1] % Mod, t = p;
		for (int j = 0; j <= i * (K - 1); t = 1ll * t * p % Mod, j++)
			res = (res + 1ll * f[i][j] * fac[j] % Mod * t) % Mod;
		res = 1ll * res * C(n, i) % Mod;
		if (i & 1) ans = (ans + res) % Mod; else ans = (ans + Mod - res) % Mod;
	}
	printf("%lld
", 1ll * ans * n % Mod);
	return 0;
}