Luogu P2791 幼儿园篮球题

自然数幂转斯特林数推式子题目。

题意：有 $n$ 个篮球，其中 $m$ 个没气，随机抽取 $k$ 个，问没气个数的 $l$ 次方的期望，对 998244353 取模。$T(T\leq 200)$ 次询问，每次询问 $l$ 相同。$n, m, k\leq 2\times 10 ^ 7, l\leq 2\times 10 ^ 5$，$ k\leq n, m\leq n$。

其实看到 $l\leq 2\times 10 ^ 5$ 和 $l$ 次方，以及每次 $l$ 相同，差不多就是斯特林数了吧……

直接一波推式子：

$$\begin{aligned} ans =& \sum_{i = 1} ^ k i ^ l \binom mi \binom{n - m}{k - i}\\ =& \sum_{i = 1} ^ k \binom mi \binom{n - m}{k - i} \sum_{j = 1} ^ i \binom ij j!{l\brace j}\\ =& \sum_{j = 1} ^ k \binom mj j!{l\brace j} \sum_{i = j} ^ k \binom{n - m}{k - i} \binom{m - j}{i - j}\\ \end{aligned}$$

然后前面的式子几乎化不了了，我们考虑计算后面的 $\sum_{i = j} ^ k\binom{n - m}{k - i}\binom{m - j}{i - j}$。容易发现枚举的上下界没有必要，因为多出来的都是 0。

考虑其组合意义，相当于我们在前面的 $n - m$ 个物品中抽出 $k - i$ 个，在后面的 $m - j$ 的物品中选出 $i - j$ 个，这相当于在 $n - m + m - j = n - j$ 个物品中，选出 $k - i + i - j = k - j$ 个物品，于是这一坨求和就可以写作 $\binom{n - j}{k - j}$。

于是答案就变成了：

$$ans = \sum_{j = 1} ^ k m ^ {\underline j} {l\brace j} \binom{n - j}{k - j}$$

看似我们需要枚举到 $k$，但是 $j > l$ 的时候显然为 0，所以 $j\leq l$ 是必需的。

大力处理一列第二类斯特林数，即可做到 $O(l\log l + Tl + N)$ 的复杂度，可以一边算答案的时候计算组合数和下降幂，省掉那个 $N$。

void initsti(int N)
{
	poly a(N + 1), b(N + 1);
	for (int i = 0; i <= N; ++ i)
		if (i & 1) a[i] = Mod - infact[i];
		else a[i] = infact[i];
	for (int i = 0; i <= N; ++ i) b[i] = (LL) qpow(i, N) * infact[i] % Mod;
	sti = a * b;
}

inline int C(int n, int m) { return n < m || n < 0 ? 0 : (LL) fact[n] * infact[m] % Mod * infact[n - m] % Mod; }

int main()
{
	int n, m, T, L, k;
	std::cin >> n >> m >> T >> L;
	initfact(n), initsti(L);
	while (T --)
	{
		scanf("%d %d %d", &n, &m, &k);
		int res = 0;
		for (int j = 1, ed = std::min(L, k); j <= ed; ++ j)
			res = (res + (LL) C(m, j) * fact[j] % Mod * sti[j] % Mod * C(n - j, k - j)) % Mod;
		res = (LL) res * qpow(C(n, k)) % Mod;
		printf("%d\n", res);
	}
	return 0;
}