Luogu P6031 Cards 加强版

比较难推式子，对斯特林数和组合数的应用要求比较高。

题意：$m$ 张牌中有一张王牌，重排 $n$ 次，求第一张是王牌的次数 $k$ 次方的期望对 998244353 取模的结果。$k\leq 10 ^ 7, n, m\leq 998244353$。

容易发现单次第一张是王牌的期望显然为 $\dfrac 1m$，令其为 $p$。

则答案可以写作：

$$\sum_{i = 0} ^ n \binom ni p ^ i(1 - p) ^ {n - i} i ^ k$$

看到 $i ^ k$，考虑使用第二类斯特林数展开，让 $k$ 下来：

$$m ^ n = \sum_{i = 0} ^ m \binom mi {n\brace i}i!$$ $$\begin{aligned} ans =& \sum_{i = 1} ^ n \binom ni p ^ i (1 - p) ^ {n - i} i ^ k\\ =& \sum_{i = 1} ^ n \binom ni p ^ i (1 - p) ^ {n - i} \sum_{j = 0} ^ i \binom ij j!{k\brace j}\\ =& \sum_{i = 1} ^ n p ^ i (1 - p) ^ {n - i} \sum_{j = 0} ^ i \dfrac{n!}{(n - i)!(i - j)!}{k\brace j}\\ =& n!\sum_{j = 0} ^ n {k\brace j} \sum_{i = j} ^ n \dfrac{p ^ i (1 - p) ^ {n - i}}{(n - i)!(i - j)!} \end{aligned}$$

考虑后面的一坨东西，我们看看能变成什么（此时 $j$ 为常量，我们写为 $a$）：

$$\begin{aligned} &\sum_{i = a} ^ n \dfrac{p ^ i (1 - p) ^ {n - i}}{(n - i)!(i - a)!}\\ =& \dfrac{1}{(n - a)!} \sum_{i = a} ^ n p ^ i (1 - p) ^ {n - i} \binom{n - a}{i - a}\\ =& \dfrac{p ^ a}{(n - a)!} \end{aligned}$$

这个式子就比较简洁了，我们带入原来的式子就是：

$$ans = n!\sum_{j = 0} ^ n {k\brace j} \dfrac{p ^ j}{(n - j)!}$$

其实现在完全可以做到 $O(k\log k)$（循环上界肯定不超过 $k$，否则为 0），良心（？）的出题人也给了一定的部分分。但是肯定跑不过 $10 ^ 7$，考虑是否做到线性递推。

容易发现 $\displaystyle {k\brace j}$ 一定是需要 $O(n\log n)$ 的，所以考虑将其砍掉。第二类斯特林数的表达方式可以用二项式反演得到，为：

$${n\brace m} = \dfrac{1}{m!}\sum_{i = 0} ^ m(-1) ^ {m - i} \binom mi i ^ n$$

但是注意这是在 $n\geq m$ 的情况下成立的，而我们枚举的 $\sum_{j = 0} ^ n {k\brace j}$ 可能是不满足的，所以我们分类讨论。

先讨论难一点的，就是 $n > k$ 的情况，这样枚举上界就变为了 $k$。

$$\begin{aligned} ans =& n!\sum_{j = 0} ^ k {k\brace j} \dfrac{p ^ j}{(n - j)!}\\ =& n!\sum_{i = 0} ^ k \dfrac{p ^ i}{i!(n - i)!} \sum_{j = 0} ^ i \binom ij (-1) ^ {i - j} j ^ k \\ =& \sum_{i = 0} ^ k p ^ i \binom ni\sum_{j = 0} ^ i\binom ij (-1) ^ {i - j} j ^ k\\ =& \sum_{i = 0} ^ k p ^ i \sum_{j = 0} ^ i (-1) ^ {i - j} j ^ k \dfrac{n!}{(n - i)!j!(i - j)!}\\ =& \sum_{j = 0} ^ k \binom nj (-1) ^ j j ^ k \sum_{i = j} ^ k (-p) ^ i \binom {n - j}{i - j}\\ =& \sum_{j = 0} ^ k \binom nj j ^ k p ^ j\sum_{i = 0} ^ {k - j} (-p) ^ i \binom {n - j}i \end{aligned}$$

推到这里，似乎我们的式子已经比较简洁了，但是后面的一坨没法使用二项式定理（上界不同），我们陷入了死胡同。

对后面这个式子硬上，考虑裂项组合数递推，设 $\displaystyle S(t) = \sum_{i = 0} ^ {k - t} (-p) ^ j\binom{n - t}{i}$。考虑大力变形：

$$\begin{aligned} S(t) =& \sum_{i = 0} ^ {k - t} (-p) ^ i \binom{n - j}{i}\\ =& \sum_{i = 0} ^ {k - t} (-p) ^ i (\binom{n - j - 1}{i - 1} + \binom{n - j - 1}{i})\\ =& (-p)\sum_{i = 1} ^ {k - t}(-p) ^ {i - 1}\binom{n - j - 1}{i - 1} + \sum_{i = 0} ^ {k - t} (-p) ^ i\binom{n - j - 1}{i} \\ S(t - 1)=& \sum_{i = 0} ^ {k - t - 1} (-p) ^ i \binom{n - j - 1}{i}\\ S(t) =& (-p)S(t + 1) + (-p) ^ {k - t} \binom{n - t - 1}{k - t} + S(t + 1)\\ S(t)=& (1 - p) S(t + 1) + (-p) ^ {k - t} \binom{n - t - 1}{k - t} \end{aligned}$$

边界显然为 $S(k) = 1$，倒序递推即可。注意 $\binom{n - t - 1}{k - t}$ 无法计算，我们可以变形：

$$\binom{n - t - 1}{k - t} = \dfrac{(n - t - 1) ^ {\underline{k - t}}}{(k - t)!} = \dfrac{(n - k) ^ {\overline {k - t}}}{(k - t)!}$$

同时计算 $S(t)$ 和上升幂并预处理 $p ^ k$，可以做到线性。

现在回来，答案可以表示为：

$$ans = \sum_{j = 0} ^ k \binom nj j ^ k p ^ i S(j)$$

维护 $n ^ \underline{j}$，即可边计算答案边计算下降幂。至此，我们解决了 $n > k$ 的情况，复杂度 $O(k)$。

下面我们计算 $n\leq k$ 的情况。

$$\begin{aligned} ans =& n!\sum_{j = 0} ^ n {k\brace j} \dfrac{p ^ j}{(n - j)!}\\ =& n!\sum_{j = 0} ^ n \dfrac{p ^ j}{(n - j)!j!} \sum_{i = 0} ^ j \binom ji(-1) ^ {i - j} i ^ k \\ =& \sum_{j = 0} ^ n p ^ j\binom nj\sum_{i = 0} ^ j \binom ji (-1) ^ {i - j} i ^ k\\ =& \sum_{i = 0} ^ n (-1) ^ i \binom ni \sum_{j = i} ^ n \binom{n - i}{j - i}(-p) ^ j i ^ k\\ =& \sum_{i = 0} ^ n p ^ ii ^ k\binom ni \sum_{j = i} ^ n \binom{n - i}{j - i} (-p) ^ {j - i}\\ =& \sum_{i = 0} ^ n p ^ ii ^ k \binom ni (1 - p) ^ {n - i} \end{aligned}$$

还是可以做到线性，可以直接计算 $\binom ni$，复杂度 $O(k)$。

void init()
{
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; ++ i) fact[i] = (LL) fact[i - 1] * i % Mod;
	infact[N - 1] = qpow(fact[N - 1]);
	for (int i = N - 2; i; -- i) infact[i] = (LL) infact[i + 1] * (i + 1) % Mod;
	
	pk[1] = 1;
	for (int i = 2; i < N; ++ i)
	{
		if (!st[i]) prime[cnt ++] = i, pk[i] = qpow(i, k);
		for (int j = 0; j < cnt && i * prime[j] < N; ++ j)
		{
			st[i * prime[j]] = true, pk[i * prime[j]] = (LL) pk[i] * pk[prime[j]] % Mod;
			if (i % prime[j] == 0) break;
		}
	}
	
	pw[0] = 1;
	for (int i = 1; i < N; ++ i) pw[i] = (LL) pw[i - 1] * p % Mod;
}

int C(int n, int m) { return (LL) fact[n] * infact[m] % Mod * infact[n - m] % Mod; }

namespace NLarge {
	void solve()
	{
		int up = 1;
		s[k] = 1;
		for (int t = k - 1; t; -- t)
		{
			up = (LL) up * (n - t - 1) % Mod;
			s[t] = (LL) (Mod + 1 - p) * s[t + 1] % Mod;
			if ((t ^ k) & 1) adj(s[t] -= (LL) up * infact[k - t] % Mod * pw[k - t] % Mod);
			else s[t] = (s[t] + (LL) up * infact[k - t] % Mod * pw[k - t]) % Mod;
		}
		
		int dn = 1, res = 0;
		for (int j = 1; j <= k; ++ j)
		{
			dn = (LL) dn * (n - j + 1) % Mod;
			res = (res + (LL) dn * infact[j] % Mod * pk[j] % Mod * pw[j] % Mod * s[j]) % Mod;
		}
		std::cout << res << std::endl;
	}
}

namespace NSmall {
	void solve()
	{
		int res = 0, cur = qpow(Mod + 1 - p, n), inv = qpow(Mod + 1 - p);
		for (int i = 1; i <= n; ++ i)
		{
			cur = (LL) cur * inv % Mod;
			res = (res + (LL) pw[i] * pk[i] % Mod * C(n, i) % Mod * cur) % Mod;
		}
		std::cout << res << std::endl;
	}
}

int main()
{
	std::cin >> n >> p >> k, p = qpow(p);
	init();
	if (n > k) NLarge::solve();
	else NSmall::solve();
	return 0;
}