洛谷题库 P6031 Cards 加强版 – 题解与思路重现

洛谷题库 P6031 Cards 加强版

对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$。

这是某场模拟考试给出的部分分：
$$
\begin{array}{cccc}
\text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline
1&n,m,k\leq 5&2&\\
2&k=1&2&\\
3&k\leq 5000&10&1,2\\
4&m\leq 100&10&1\\
5&n\leq k&5&\\
6&k\leq 10^5&10&1,2,3\\
7&k\leq 5\times 10^6&20&1,2,3,6\\
8&&41&1\sim 7
\end{array}
$$

部分分

我首先考虑的是期望的线性性。

记 $E_n(x^k)$ 为洗牌 $n$ 次，获胜场次的 $k$ 次方的期望。考虑下一场的胜负情况。对于 $n>0$，有转移
$$\begin{aligned}
E_n(x^k)&=\frac{m-1}{m}E_{n-1}(x^k)+\frac{1}{m}E_{n-1}\left((x+1)^k\right)\\
&=\frac{m-1}{m}E_{n-1}(x^k)+\frac{1}{m}E_{n-1}\left(\sum_{i=0}^k\binom{k}{i}x^i\right)\\
&=\frac{m-1}{m}E_{n-1}(x^k)+\frac{1}{m}\sum_{i=0}^k\binom{k}{i}E_{n-1}(x^i)\\
&=E_{n-1}(x^k)+\frac{1}{m}\sum_{i=0}^{k-1}\binom{k}{i}E_{n-1}(x^i)
\end{aligned}$$

想象一张无穷大的网格图：第 $n$ 列第 $k$ 行表示的是 $E_n(x^k)$。对于每个点 $(n,k)\ \ (n>0,k\geq 0)$，我们设立 $k$ 条边 $(n-1,i)\rightarrow(n,k)$（$i$ 取遍 $0,1,\cdots,k-1$），边权分别为 $\binom{k}{i}/m$，称经过它们为大跳；同时有边 $(n-1,k)\rightarrow(n,k)$，边权为 $1$。定义一条路径的权值为路径上所有边的边权之积。又有 $E_0(x^k)=[k=0]$，于是由上文转移式得到 $E_n(x^k)$ 等于在网格图上从 $(0,0)$ 到 $(n,k)$ 的所有合法路径的权值之和。又因为非大跳的权值为 $1$，故我们只需考虑大跳的起终点。设某条路径有 $c$ 次大跳，每次大跳落点为 $p_0=0,p_1,p_2,\cdots,p_c=k$。那么，这条路径的权值为
$$\begin{aligned}
&\prod_{i=1}^c \frac 1m\binom{p_i}{p_{i-1}}\\
=&\frac{1}{m^c}\binom{p_c}{p_c-p_{c-1}}\binom{p_{c-1}}{p_{c-1}-p_{c-2}}\cdots\binom{p_2}{p_2-p_1}\binom{p_1}{p_1}\\
=&\frac{1}{m^c}\binom{k}{p_1-p_0,p_2-p_1,\cdots,p_c-p_{c-1}}&(p_c=k)\\
=&\frac{k!}{\prod_{i=1}^c\frac 1m(p_i-p_{i-1})!}
\end{aligned}$$

于是我们不妨修改每条大跳边 $(n-1,k-\Delta)\rightarrow(n,k)\ \ (\Delta>0)$ 的权值为 $\frac{1}{m\Delta!}$，$E_n(x^k)$ 的实际值为路径权值和与 $k!$ 的积。

$\text{24 pts}$ – I – $k\leq 10^5$，生成函数与多项式快速幂

注意到从 $(n-1,k)$ 转移到 $(n,k+\Delta)$ 的权只与 $\Delta$ 有关，自然想到生成函数的卷积。我们构造数列 $\langle f_n\rangle$，满足 $f_0=1,f_i=\frac{1}{m\cdot i!}\ \ (i>0)$。记 $F(z)=1+\frac{1}{m}z+\frac{1}{2!m}z^2+\cdots$ 为它的普通生成函数，则有 $E_n(x^k)=k!\cdot [z^k]F^n(z)$。

暴力求取快速幂，复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(k\log^2 k)$；使用多项式 $\exp,\ln$ 优化到 $\bigO(k\log k)$。

$\text{24 pts}$ – II – 多项式乘法

我们直接对所有路径的权值求和。枚举 $c$，“枚举”所有合法落点序列（的差分形式），考虑大跳是在 $n$ 次转移的哪些位置进行的，得到如下式子：
$$\begin{aligned}
E_n(x^k)=&\sum_{c=0}^{\min\{n,k\}}\binom{n}{c}\frac{1}{m^c}\sum_{\substack{\Delta_1+\cdots+\Delta_c=k,\\ \forall i,0<i\leq c,\Delta_i>0}}\binom{k}{\Delta_1,\Delta_2,\cdots,\Delta_c}
\end{aligned}$$

$\forall i,0<i\leq c,\Delta_i>0$ 的限制很烦。若没有它，那么不难得到
$$
\sum_{\Delta_1+\cdots+\Delta_c=k}\binom{k}{\Delta_1,\Delta_2,\cdots,\Delta_c}=(\underbrace{1+1+\cdots+1}_{c\text{ 个 }1})^k=c^k
$$
考虑以该简化形式为基础，使用容斥原理计算带有 $\Delta_i>0$ 限制的结果。我们钦定其中 $i$ 个位置满足 $\Delta_j=0$。于是剩下的 $c-i$ 个 $\Delta_j$ 之和为 $k$，是为 $c-i$ 项式系数，也即
$$
\sum_{\Delta_1+\cdots+\Delta_{c-i}=k}\binom{k}{\Delta_1,\Delta_2,\cdots,\Delta_{c-i},\underbrace{0,\cdots,0}_{i\text{ 个 }0}}=(c-i)^k
$$
考虑从 $c$ 个位置中选取这 $i$ 个位置，乘上容斥系数，得到答案为
$$
\tag{1}E_n(x^k)=\sum_{c=0}^{\min\{n,k\}}\binom{n}{c}\frac{1}{m^c}\sum_{i=0}^{c}(-1)^i\binom{c}{i}(c-i)^k
$$

内部的和式可以被改写为 $c!\sum_{i=0}^c\left((-1)^i/i!\right)\left((c-i)^k/(c-i)!\right)$，可以用多项式乘法优化卷积。时间复杂度 $\bigO(k\log k)$。

优化多项式乘法得到的另解

就算时间给够，我们似乎也不能简单地用 NTT（$\mathbb{Z}/n\mathbb{Z},n=998244353$ 域上）计算 $k\geq 2^{22}$ 时的卷积。原因很简单：这个群的阶只有 $2^{23}$ 的偶因数。但学习了宋佳兴学长的代码后发现，我们可以将数列作拆分：$F(z)=F_0(z)+z^{2^l}F_1(z)+z^{2\times 2^l}F_2(z)+\cdots$ 然后将每一部分分别相乘后再相加，就能得到正确的卷积结果。

常数优化

• 手写不带分支的取模函数（用数的符号位判断是否应补全/减去 $P=998244353$）；
• （NTT 过程中）不要每一次迭代时重新计算 $\bigO(n\log n)$ 次原根的次幂，可以预处理后花费 $\bigO(n\log n)$ 的空间存下来。

时间复杂度 $\bigO(kl+\lceil k/2^l\rceil^2k)$（点值相乘后直接相加，最后再 IDFT 以省时），尝试后发现 $l=19$ 时较快。

正解

直接从期望的定义下手：所有情况下 $x^k$ 的和除以情况总数。枚举 $x$，那么答案为
$$
E_n(x^k)=\frac{\sum_{x=0}^{n}x^k\binom{n}{x}(m-1)^{n-x}}{m^n}=\left(\frac{m-1}{m}\right)^n\sum_{x=0}^nx^k\binom{n}{x}\frac{1}{(m-1)^x}
$$

暴力计算该式答案，将得到 $\text{5 pts}$ 的好成绩（$n\leq k$）。我们希望得到 $\bigO(k)$ 的算法，故尝试将 $x^k$ 用第二类斯特林数转化为下降幂：
$$\begin{aligned}
x^k&=\sum_{c=0}^kx^{\underline c}\begin{Bmatrix}k\\c\end{Bmatrix}=\sum_{c=0}^kx^{\underline c}\frac{(-1)^c}{c!}\sum_{i=0}^c(-1)^i\binom ci i^k\\
\text{原式}&=\left(\frac{m-1}{m}\right)^n\sum_{x=0}^n\binom{n}{x}\frac{1}{(m-1)^x}\sum_{c=0}^kx^{\underline c}\frac{(-1)^c}{c!}\sum_{i=0}^c(-1)^i\binom ci i^k\\
&=\left(\frac{m-1}{m}\right)^n\sum_{c=0}^k\frac{(-1)^c}{c!}\left(\sum_{i=0}^c(-1)^i\binom ci i^k\right)\boxed{\sum_{x=0}^{n}\binom{n}{x}\frac{x^{\underline c}}{(m-1)^x}}
\end{aligned}$$
化简方框内和式：
$$\begin{aligned}
\sum_{x=0}^{n}\binom{n}{x}\frac{x^{\underline c}}{(m-1)^x}&=\sum_{x=0}^{n}\frac{n!}{x!(n-x)!}\frac{x!}{(x-c)!}\frac{1}{(m-1)^x}\\
&=\sum_{x=c}^n\binom{n-c}{x-c}\frac{n^{\underline c}}{(m-1)^x}\\
&=\sum_{x=0}^{n-c}\binom{n-c}x\frac{n^{\underline c}}{(m-1)^{x+c}}\\
&=n^{\underline c}\frac{1}{(m-1)^c}\left(\frac{m}{m-1}\right)^{n-c}=n^{\underline c}\frac{m^{n-c}}{(m-1)^n}
\end{aligned}$$
$$\begin{aligned}
\text{原式}&=\left(\frac{m-1}{m}\right)^n\sum_{c=0}^k\frac{(-1)^c}{c!}n^{\underline c}\frac{m^{n-c}}{(m-1)^n}\sum_{i=0}^c(-1)^i\binom ci i^k\\
&=\sum_{c=0}^{\min\{n,k\}}\binom{n}{c}\frac{1}{(-m)^c}\sum_{i=0}^c(-1)^i\binom ci i^k
\end{aligned}$$

与部分分解法式 $(1)$ 殊途同归。现在考虑它的化简。记 $\newcommand\lmt{\text{lmt}}\lmt=\min\{n,k\}$。$\binom{n}{c}\binom{c}{i}$ 惹人注意，我们尝试交换求和顺序并交换指标：
$$\begin{aligned}
\text{原式}&=\sum_{i=0}^{\lmt}(-1)^ii^k\sum_{c=i}^{\lmt}\binom nc\binom ci\frac{1}{(-m)^c}\\
&=\sum_{i=0}^{\lmt}(-1)^ii^k\binom ni\sum_{c=i}^{\lmt}\binom{n-i}{c-i}\frac{1}{(-m)^c}\\
&=\sum_{i=0}^{\lmt}(-1)^ii^k\frac{1}{(-m)^i}\sum_{c=0}^{\lmt-i}\binom{n-i}c\frac{1}{(-m)^c}
\end{aligned}$$

记 $h(i)=\sum_{c=0}^{\lmt-i}\binom{n-i}c\frac{1}{(-m)^c}$。假若 $\lmt=n$，也即 $n\leq k$，那么显然有 $h(i)=\left(1+\frac{1}{-m}\right)^{n-i}=\left(\frac{m}{m-1}\right)^{n-i}$；否则似乎难以求出它的封闭形式。但我们发现在 $i$ 不同时，变化的只有二项式系数的上指标。根据递推公式 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\ \ (n,m>0)$ 以及 $\binom n0=1\ \ (n\geq 0)$，我们尝试从 $h(i+1)$ 转移到 $h(i)\ \ (i<\lmt)$。转写为
$$\begin{aligned}
h(i)&=\sum_{c=0}^{\lmt-i}\binom{n-i}c\frac{1}{(-m)^c}\\
&=\binom{n-i}0\frac{1}{(-m)^0}+\sum_{c=1}^{\lmt-i}\left(\binom{n-(i+1)}c+\binom{n-(i+1)}{c-1}\right)\frac{1}{(-m)^c}\\
&=\binom{n-(i+1)}0\frac{1}{(-m)^0}+\left(\sum_{c=1}^{\lmt-i}\binom{n-(i+1)}c\frac{1}{(-m)^c}\right)+\frac{1}{-m}\left(\sum_{c=0}^{\lmt-(i+1)}\binom{n-(i+1)}c\frac{1}{(-m)^c}\right)\\
&=\left(h(i+1)+\binom{n-(i+1)}{\lmt-i}\frac{1}{(-m)^{\lmt-i}}\right)-\frac 1mh(i+1)
\end{aligned}$$
$$
\text{answer}=\sum_{i=0}^{\lmt}(-1)^ii^k\frac{1}{(-m)^i}h(i)
$$

$h(\lmt)$ 可以在 $\bigO(\lmt)$ 的时间内算出；而所有上指标与 $n$ 相关的二项式系数，下指标均不超过 $\lmt\leq k$，可以通过下降幂等递推求出。于是我们可以 $\bigO(k)$ 的时间计算出本题答案。

R99501601 记录详情

以下代码因省空间省时间而可读性较差，仅供参考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

#define inl __always_inline
typedef unsigned long long ull;
using ulll = __uint128_t;

constexpr uint N = 1e7 + 10, P = 998244353;
uint n, m, k, p[N], pk[N], fac[N], *ppt = p; ulll ans;
constexpr uint *const inv = p, *const f = fac;

inl ull fpow (ull a, ull b) {
	ull c = 1; a %= P;
	for (; b; b >>= 1) {
		if (b & 1) (c *= a) %= P;
		(a *= a) %= P;
	}
	return c;
}
inl void calc_inv () {
	constexpr uint *const fact = inv;
	fact[0] = 1;
	for (ull x = 1; x < N; ++x)
		fact[x] = fact[x-1] * x % P;
	ull finv = fpow (fact[N-1], P-2);
	for (ull x = N-1; x; --x)
		inv[x] = finv * fact[x-1] % P,
		(finv *= x) %= P;
}
inl void sieve () {
	pk[1] = 1;
	for (ull x = 2, _pk, y; x < N; ++x) {
		if (!fac[x]) fac[x] = *ppt++ = x,
			pk[x] = fpow (x, k);
		_pk = pk[x];
		for (uint *pt = p; pt != ppt && (y = *pt*x) <= N-1
			&& fac[x] >= *pt; ++pt)
			fac[y] = *pt,
			pk[y] = _pk * pk[*pt] % P;
	}
}

int main () {
	/*  */
	scanf ("%u%u%u", &n, &m, &k);
	const uint lmt = min (n, k), invm = fpow (m, P-2),
		minvm = invm * (P-1ull) % P;
	sieve (); calc_inv (); f[lmt+1] = 0;
	uint *pt1 = inv, *_f = f + lmt, *pt2 = pk;
	ull p = lmt, co = 1;
	while (~p)
		*_f = (_f[1] * (minvm + 1ull) + co) % P, --_f,
		co = co * (n-p--) % P * *++pt1 % P * minvm % P;
	pt1 = inv, _f = f, p = 0, co = 1;
	while (p <= lmt)
		ans += co * *pt2++ * (ulll) *_f++,
		(co *= *++pt1 * (n-p++) % P * invm % P) %= P;
	printf ("%llu", ull (ans % P));

	return 0;
}