[uoj514]通用测评号

小 R 是养鸽子的人。一天，小 R 给鸽子们喂玉米吃。一共有 $n$ 只鸽子，小 R 每秒会等概率选择一只没有吃撑的鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量 $\geq b$，一只鸽子吃撑了当且仅当它吃了的玉米粒数量 $\geq a$。

小 R 想要你告诉他，当所有鸽子都吃饱时，期望有多少只鸽子吃撑了。

输入格式

输出格式

输出一行一个整数，表示吃撑的鸽子的期望数量在模 $998244353$ 意义下的结果。

题解

首先，由期望的线性性，将问题转化为当所有鸽子都吃饱时，一只鸽子吃撑的概率，设结果为 $p$，则最终的答案就是 $n \cdot p$。

不妨固定吃撑的鸽子为 $1$ 号鸽子，那么事件 "所有鸽子吃饱时，鸽子 $1$ 已经吃撑" 等价于 "鸽子 $1$ 吃撑的时候，还有鸽子没吃饱"。

考虑使用容斥原理，固定除了 $1$ 号鸽子外，还有 $i$ 只鸽子没有吃饱。不难得到容斥系数为 $1$，加上枚举集合，答案的表达式就为 $$ ans = n \cdot \sum_{i=1}^{n-1} \left( -1 \right)^{i-1} \binom {n - 1} i p_{i+1} $$

其中 $p_m$ 表示共有 $m$ 只鸽子，其中鸽子 $1$ 吃撑的时候，其余 $m - 1$ 只鸽子都没有吃饱的概率。

根据套路，接下来考虑求 $p_m$。我们枚举一共投入了 $i$ 粒玉米，这样就一共有 $m^i$ 种可能情形 (玉米序列)。

考虑玉米序列 $c_1, c_2, \cdots, c_i$ ($1 \leq c_j \leq m$)，根据定义，玉米序列是合法的，当且仅当其中 $1$ 出现了恰好 $A$ 次，其余数出现不得超过 $B - 1$ 次。

艾玛，换汤不换药。列出指数生成函数，可知合法的玉米序列数就等于 $$ \left( i - 1 \right) ! \left[ x^{i-1} \right] \left( \frac {x^A} {A !} \cdot \left( 1 + x + \frac {x^2} {2 !} + \frac {x^3} {3 !} + \cdots + \frac {x^{B - 1}} {\left( B - 1 \right) !} \right)^{m - 1} \right) $$

至于如何求多项式 $f \left( x \right) = 1 + x + \dfrac {x^2} {2 !} + \dfrac {x^3} {3 !} + \cdots + \dfrac {x^{k - 1}} {\left( k - 1 \right) !}$ 的幂次，在那道题中已经提到过，使用求导的珂(tao)技(lu)即可在 $O \left( n^2 B \right)$ 时间内解决，这里就不再赘述了。

最后考虑拼答案。首先，对于枚举的 $m, i$，一共有 $\left( i - 1 \right) ! \left[ x^{i-1} \right] \left( \dfrac {x^A} {A !} \cdot f^{m-1} \left( x \right) \right)$ 种合法的玉米序列，每种合法的玉米序列对概率的贡献为 $\dfrac 1 {m !}$，将二者相乘，就得到这一对 $\left( m, i \right)$ 对答案的贡献：$$ \left( i - 1 \right) ! \left[ x^{i-1} \right] \left( \frac {x^A} {A !} \cdot f^{m-1} \left( x \right) \right) \cdot \frac 1 {m^i} $$

将 $i$ 从 $A$ 到 $\left( m - 1 \right) \left( B - 1 \right) + A$ 求和，就是 $p_m$ 的值 ($m$ 只鸽子时，鸽子 $1$ 吃撑时其余鸽子都没吃饱的概率)。

于是我们成功求出了所有 $p_m$，整个问题就可以在 $O \left( n^2 B \right)$ 时间内解决。

代码

// copy and edit from [uoj449]喂鸽子.
#include <bits/stdc++.h>

typedef long long ll;
const int N = 254, NK = 64000, mod = 998244353;

int n, A, K;
int fact[NK], inv[NK], finv[NK];
int f[N][NK], g[N][NK];
/*
	Let A(x) = 1 + x + x^2/2! + x^3/3! + ... + x^(k-1)/(k-1)!.
	f[i][j] = [x^j] A^i(x)
	g[i][j] = [x^j] x^(k-1)/(k-1)! A^i(x)
*/

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init() {
	int i, j;
	for (inv[1] = 1, i = 2; i <= n * K; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
	for (*finv = *fact = i = 1; i <= n * K; ++i) fact[i] = (ll)fact[i - 1] * i % mod, finv[i] = (ll)finv[i - 1] * inv[i] % mod;
	**f = 1, g[0][K - 1] = finv[K - 1];
	for (i = 1; i <= n; ++i)
		for (g[i][K - 1] = finv[K - 1], *f[i] = j = 1; j <= i * (K - 1); ++j)
			f[i][j] = (ll)(f[i][j - 1] - g[i - 1][j - 1] + mod) * i % mod * inv[j] % mod,
			g[i][j + K - 1] = (ll)f[i][j] * finv[K - 1] % mod;
	for (i = 1; i <= n; ++i) {
		memset(g[i], 0, (A - 1) << 2);
		for (j = 0; j <= i * (K - 1); ++j)
			g[i][j + A - 1] = (ll)f[i][j] * finv[A - 1] % mod;
	}
}

inline ll C(int n, int r) {return (ll)fact[n] * finv[r] % mod * finv[n - r] % mod;}

int get(int m) {
	int i, ret = 0; ll coe = PowerMod(m, mod - 1 - A, n);
	for (i = A; i <= (m - 1) * (K - 1) + A; ++i)
		ret = (ret + coe * fact[i - 1] % mod * g[m - 1][i - 1]) % mod, coe = coe * inv[m] % mod;
	return ret;
}

int main() {
	int i; ll t, ans = 0;
	scanf("%d%d%d", &n, &A, &K), init();
	for (i = 1; i < n; ++i) t = C(n - 1, i) * get(i + 1) % mod, i & 1 ? ans += t : ans -= t;
	ans %= mod, printf("%lld\n", ans + (ans >> 63 & mod));
	return 0;
}

坑

坑1：注意生成函数中最前面的一项是 $\dfrac {x^A} {A !}$，因此在计算时系数不要搞错。

题目描述

输入格式

输出格式

题解

代码

坑