组合数学总结

本篇文章是为了总结一下最近做的组合数学的题目以及涉及到的知识点，以后可能会不定期补充。

同时也参考了大佬 lyt 的博客。同时如果想要更深入地了解组合数学中的推式子技巧，可以看下 pjw 的博客。地址1 地址2

基本知识

排列数 $A_n^m$ 表示从 $n$ 个不同的物品中选出 $m$ 个组成的不同排列的数量。$A_n^m=\frac{n!}{(n-m)!}$。

组合数（高中常用 $C_n^m$ 来表示，但是目前通常用 $\dbinom{n}{m}$ 表示），表示从 $n$ 个不同物品中选出 $m$ 个物品的方案数。$\dbinom{n}{m} = \frac{n!}{m!(n-m)!}$。

二项式定理：$(x+y)^n=\sum \limits_{i=0}^n\dbinom{n}{i}x^iy^{n-i}$。

一些比较重要的组合数等式

1. $\dbinom{n}{m} = \dbinom{n}{n-m}$
2. $\sum \limits_{i=0}^n \dbinom{n}{i}=2^n$。二项式定理当 $x=y=1$ 时的情况。
3. $\sum \limits_{i=0}^n (-1)^i\dbinom{n}{i}=[n=0]$。二项式定理当 $x=1, y=-1$ 时的情况。
4. $\dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k}$。从组合意义上即可证明。
5. $\sum \limits_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}$。范德蒙德卷积，组合意义上证明即可。
6. $\sum \limits_{i=0}^n\dbinom{i}{m}=\dbinom{n+1}{m+1}$。
7. $\dbinom{n}{m}=\dbinom{n-1}{m-1}+\dbinom{n-1}{m}$。

二项式反演

设 $f_n$ 为恰好 $n$ 个元素组成特定结构的方案数，$g_n$ 为从 $n$ 个元素中选出 $i$ 个元素组成特定结构的方案数，显然 $g_n=\sum \limits _{i=0}^n\dbinom{n}{i}f_i$。则 $f_n=\sum \limits _{i=0}^n(-1)^{n-i}\dbinom{n}{i}g_i$。

（$f_i$ 恰好，$g_i$ 至多）

---

证明如下（直接从十二重计数法那搬过来的）

$$\begin{aligned}\sum \limits_{i=0}^n\dbinom{n}{i}(-1)^{n-i}f(i)&=\sum \limits_{i=0}^n\dbinom{n}{i}(-1)^{n-i} \sum \limits_{j=0}^i \dbinom{i}{j}g(j)\\&= \sum \limits_{i=0}^n \sum \limits_{j=0}^i\dbinom{n}{i}\dbinom{i}{j}(-1)^{n-i}g(j)\\&= \sum \limits_{i=0}^n\sum \limits_{j=0}^i \dbinom{n}{j}\dbinom{n-j}{i-j}(-1)^{n-i}g(j)\\&=\sum \limits_{j=0}^n \dbinom{n}{j}g(j)\sum \limits_{i=j}^n \dbinom{n-j}{i-j}(-1)^{n-i}\\&=\sum \limits_{j=0}^n \dbinom{n}{j}g(j)\sum \limits_{i=0}^{n-j} \dbinom{n-j}{i}(-1)^{n-i-j}\\&=\sum \limits_{j=0}^n \dbinom{n}{j}g(j)\times 0^{n-j}\\&= g(n)\end{aligned}$$

据说也可以用 EGF 证，但是我不会（

---

二项式反演的另一种常见形式：

设 $f_i$ 为恰好 $i$ 个条件满足的方案数，$g_i$ 为至少 $i$ 个条件满足的方案数（也就是强制让 $i$ 个条件满足后其他的随便），则显然 $g_k=\sum \limits _{i=k}^n\dbinom{i}{k}f_i$，那么 $f_k=\sum \limits _{i=k}^n(-1)^{i-k}\dbinom{i}{k}g_i$。

（$f_i$ 恰好，$g_i$ 至少）

同时，当 $k=0$ 时，$f_0=\sum \limits _{i=0}^n(-1)^{i}g_i$。因此容斥原理其实是二项式反演的一种特殊情况。

多重集排列数

设多重集 $S=\{n_1\cdot x_1,n_2\cdot x_2, \cdots ,n_k\cdot x_k \}$，则该多重集的全排列数量为 $\frac{n!}{n_1!n_2!n_3!\cdots n_k!}(n=\sum n_i)$。

多重集组合数

从集合 $S=\{n_1\cdot x_1,n_2\cdot x_2, \cdots ,n_k\cdot x_k \}$ 中选出 $m$ 个数的方案数。

我们可以把问题转化成另一个形式：$n_1+n_2+\cdots +n_k=m$，求正整数解的个数。

多重集组合数分两种情况，没有上界和有上界。

先分析没有上界的情况，也就是 $n_i=\infty$ 时，我们可以把它转化成插板法，方案数即为 $\dbinom{m+k-1}{m-1}$。

再分析有上界的情况。

当 $\forall i\in [1,k],n_i\le r_i$ 时，我们可以用容斥把约束干掉。依次考虑哪些约束被选中，然后删去这些约束后用无上界的情况解决，最后容斥原理即可。

公式太长了不放了

卡特兰数

原始定义：$Cat_n=\sum \limits _{x+y=n-1}Cat_xCat_y$。

递推公式：$Cat_n=\frac{4n-2}{n+1} Cat_{n-1}$。

通项公式：$Cat_n=\dbinom{2n}{n}-\dbinom{2n}{n+1}$。

以下问题的解均为卡特兰数：

1. 大小为 $n$ 的二叉树数量。
2. 凸 $n+2$ 边形的三角剖分数量。
3. $n$ 个元素进栈出栈的排列数量。
4. 从 $(0,0)$ 走到 $(n,n)$，每次只能向右或向上走，且不能越过 $y=x$ 这条线的方案数。

如果想要更详细的卡特兰数讲解，可以看 pjw 的博客。这里不过多讲解。

错位排列

设满足长度为 $n$ 且满足 $\forall i\in [1,n],p_i\not= i$ 的排列数量为 $D_n$，则 $D_n=(n-1)(D_{n-1}+D_{n-2})$，或者 $D_n=n D_{n-1} + (-1)^{n}$.

我们设 $f_n$ 为恰好 $n$ 个位置错开，$g_n$ 为至多 $n$ 个位置错开。易知 $g_n=n!$。根据二项式反演可以得到 $f_n=\sum \limits _{i=0}^n(-1)^{n-i}\dbinom{n}{i}i!$。

斯特林数

第二类斯特林数

第二类斯特林数 $n\brace m$ 表示将 $n$ 个不同元素划分成 $m$ 个相同的非空集合的方案数。

递推公式为 ${n\brace m}={n-1\brace m-1}+m{n-1\brace m}$。表示枚举将最后加入的一个元素另开一个集合还是加入原来的集合。

通项公式为：${n\brace m}=\sum \limits _{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}$。直接用下面的等式中第一个二项式反演一下即可。

$$m^n= \sum \limits _{i=0}^{m\ \mathrm{or} \ n}{n\brace i}i!\dbinom{m}{i}$$

可以类比十二重计数法中的情况，$m^n$ 表示将 $n$ 个不同的小球放入 $m$ 个不同的盒子中，我们可以枚举有 $i$ 个盒子装了小球，斯特林数为装起来的方案数，再考虑盒子的排列 $i!$，同时再考虑选出哪些盒子。就能得到这个等式。这个等式在化简一些 $x^k$ 的式子中十分有用。

$$\begin{aligned} \sum \limits_{i=0}^n i^k&=\sum \limits_{i=0}^{n} \sum \limits _{j=0}^k {k\brace j}j!\dbinom{i}{j} \\ &=\sum \limits _{j=0}^k{k\brace j}j! \sum \limits _{i=0}^n \dbinom{i}{j}\\ &= \sum \limits _{j=0}^k{k\brace j}j!\dbinom{n+1}{j+1} \end{aligned}$$

我们也可以得到自然数幂求和的一个结论：

$$\begin{aligned} \sum \limits _{i = 0}^ni^k & = \sum \limits _{i = 0}^n\sum \limits _{j = 0}^k {k \brace j}j!\dbinom{i}{j}\\ &= \sum \limits _{j=0}^k{k\brace j}j!\sum \limits _{i=0}^n\dbinom{i}{j}\\ &= \sum \limits _{j=0}^k{k\brace j}j!\dbinom{n+1}{j+1} \end{aligned}$$

第一类斯特林数

第一类斯特林数 ${n\brack m}$ 为将 $n$ 个不同元素划分为 $m$ 个不区分的环的方案数。（环的意思就是可以轮换，比如 $1,2,3,4,5$ 和 $5,1,2,3,4$ 就是一个环）

递推公式：${n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}$。枚举将一个新元素放入原有的环或者新开一个环。

第一类斯特林数没有实用的通项公式。

本来这里想咕掉不写斯特林的一些科技的，直到我发现 2020 年省选考了下降幂

上升幂与下降幂

下降幂：$x^{\underline{n}}=\frac{x!}{(x-n)!} = {\prod_{i=0}^{n-1}(x-i)}$。

上升幂：$x^{\bar{n}}={\prod_{i=0}^{n-1}(x+i)}$。

下降幂性质：$m^{\underline{k}}\dbinom{n}{m} = \dbinom{n-k}{m-k}n^{\underline{k}}$。

证明：

$$\begin{aligned} m^{\underline{k}}\dbinom{n}{m} &= \frac{m!}{(m-k)!}\frac{n!}{m!(n-m)!} \\ &=\frac{(n-k)!}{(m-k)!(n-m)!}\frac{n!}{(n-k)!}\\ &=\dbinom{n-k}{m-k}n^{\underline{k}} \end{aligned}$$

下降幂上升幂互换：$x^{\underline{n}}=(-1)^n(-x)^{\bar{n}}$。

普通幂转下降幂：$x^n=\sum \limits _{i=0}^n {n\brace i}x^{\underline{i}}$。下降幂转普通幂：$x^{\underline{n}}=\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}x^{i}$。

普通幂转上升幂：$x^{n}=\sum \limits _{i=0}^n (-1)^{n-i}{n\brace i}x^{\bar{i}}$。上升幂转下降幂：$x^{\bar{n}}=\sum \limits _{i=0}^n {n\brack i}x^{i}$。

---

对第二个式子和第四个式子的证明：

第二个式子：

考虑数学归纳法

$$\begin{aligned}x^{\underline{n+1}}&=(x-n)x^{\underline{n}}\\&=(x-n)\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}x^{i}\\&=x\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}x^{i}-n\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}x^{i}\\&=\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}x^{i+1}-n\sum \limits _{i=0}^{n+1} (-1)^{n-i}{n\brack i}x^{i}\\&=\sum \limits _{i=1}^{n+1} (-1)^{n-i+1}{n\brack i-1}x^{i}+n\sum \limits _{i=1}^{n+1} (-1)^{n-i+1}{n\brack i}x^{i}\\&=\sum \limits _{i=1}^{n+1}({n\brack i-1}+n{n\brack i})(-1)^{n-i+1}x^i\\&=\sum \limits _{i=1}^{n+1}{n+1\brack i}(-1)^{n+1-i}x^i\\&=\sum \limits _{i=0}^{n+1}{n+1\brack i}(-1)^{n+1-i}x^i\end{aligned}$$

第四个式子可以把上升幂转下降幂，再用第二个式子的结论。

$$\begin{aligned} x^{\bar{n}} &= (-1)^n(-x)^{\underline{n}}\\ &=\sum \limits _{i=0}^n{n\brack i} (-1)^n (-1)^{n-i} (-x)^i\\ &=\sum \limits _{i=0}^n{n\brack i}x^i \end{aligned}$$

---

斯特林反演

若 $g_n=\sum \limits _{i=0}^n{n\brace i}f_i$，则 $f_n=\sum \limits _{i=0}^n (-1)^{n-i}{n\brack i}g_i$。

斯特林反演不太常用，可以暂时不掌握。

题目

组合数学不是会数数就行吗
我觉得组合数学它都不能叫做数学
你高中三年数学不学都会组合数学
------------------------- 白宇

基础组合数学

[SDOI2016] 排列计数

求有多少种 $1 \sim n$ 的排列满足恰好有 $m$ 个位置满足 $a_i=i$。

数据范围：$T \le 5\times 10^5, n, m\le 1 \times 10^6$。

---

原排列除去这 $m$ 个位置就是一个错位排列，直接用递推公式求。而我们要从 $n$ 个位置中选出 $m$ 个位置不动，总方案数就为 $D_{n-m}\dbinom{n}{m}$。预处理即可。时间复杂度 $O(T+n)$

[NOI Online #2 入门组] 建设城市

求满足以下条件的长度为 $2n$ 的序列 $a$ 的个数：最大值不超过 $m$，前 $n$ 个数单调不降，后 $n$ 个数单调不增，且 $a_x=a_y$。

数据范围：$n \le 2\times 10^5$。

---

我们可以枚举 $x$ 位置的高度，假设当前枚举到的高度为 $i$，之后分情况讨论：

当 $x \le n \le y$ 时，整个序列被 $x, y$ 分成了四段。我们只拿出 $[1,x-1]$ 这一段来讨论，其他段同理。我们可以把 $[1,x-1]$ 这些城市看成小球，每个高度看成不同的盒子。因为最后都要保持有序，我们不妨把小球都看成相同的。我们就转化成了一个经典模型，插板法即可，方案数为 $\dbinom{x-1+i-1}{i-1}$。

当 $x < y < n$ 或 $n < x < y$ 时，我们可以把 $x\sim y$ 这些建筑看成一个建筑，然后像上面的方法计算即可。

时间复杂度 $O(n)$。

[HAOI2011]Problem c

有 $n$ 个人，每个人有一个座位 $a_i$。现在从 $1\sim n$ 依次入座，如果他要坐的地方已经有人了，他就会依次尝试 $a_i + 1, a_i + 2$，依此类推。如果一直尝试到 $n$ 都没有座位，那么该方案就不合法。现在已经确定了 $m$ 个人的座位，求合法方案数。

数据范围：$n \le 300$。

---

首先考虑无解的情况，我们设 $sum_i$ 表示已经确定的编号大于等于 $i$ 的人数。当 $sum_i > n - i + 1$ 时无解。再考虑有解的情况。我们设 $f_{i, j}$ 为剩余编号大于等于 $i$ 的人中已经确定了 $j$ 个人的座位。我们枚举 $k$ 表示当前选 $k$ 个人的编号为 $i$。我们就有转移方程 $f_{i,j}=\sum \limits _{k=0}^j \dbinom{j}{k} f_{i+1,j-k}(0\le j \le n-i+1-sum_i)$。答案即为 $f_{1, n-m}$。

[SHOI2015]超能粒子炮·改

求 $\sum \limits _{i=0}^k\dbinom{n}{i}\bmod 2333$。

---

设 $f_{n, k} = \sum \limits _{i=0}^k\dbinom{n}{i}\bmod 2333$。

开始大力推式子

$$\begin{aligned} f_{n,k}&=\sum\limits _{i=0}^k \dbinom{n}{i}\bmod p\\ &=\sum \limits _{i=0}^k\dbinom{n/p}{i/p}\dbinom{n\bmod p}{i \bmod p}\\ &=\dbinom{n/p}{0}\sum \limits_{i=0}^{p-1}\dbinom{n\bmod p}{i} +\dbinom{n/p}{1}\sum \limits_{i=0}^{p-1}\dbinom{n\bmod p}{i}+\cdots+\dbinom{n/p}{k/p-1}\sum \limits_{i=0}^{p-1}\dbinom{n\bmod p}{i}+\dbinom{n/p}{k/p}\sum \limits_{i=0}^{k \bmod p}\dbinom{n\bmod p}{i}\\ &=\sum \limits _{i=0}^{p-1}\dbinom{n \bmod p}{i}\times\sum \limits_{i=0}^{k/p-1}\dbinom{n/p}{i}+\dbinom{n/p}{k/p}\sum \limits_{i=0}^{k \bmod p}\dbinom{n\bmod p}{i}\\ &=f_{n \bmod p, p-1}\times f_{n/p, k/p-1}+\dbinom{n/p}{k/p} f_{n \bmod p, k \bmod p} \end{aligned}$$

我们就可以递推出前 $2333$ 项的 $f$，然后用类似卢卡斯定理的方式求解即可。

[CQOI2018]交错序列

交错序列的定义是：只由 $0$ 和 $1$ 组成的一个序列，且序列中所有 $1$ 都互不相邻。一个交错序列的权值为：设 $0$ 的个数为 $x$ 个，$1$ 的个数为 $y$ 个，那么权值即为 $x^ay^b$（$a, b$ 为给定的整数）。求长度为 $n$ 的所有交错序列的权值和。

数据范围：$n \le 10^7$。

---

我们枚举 $1$ 的个数，考虑有 $x$ 个 $1$ 的交错序列的个数。我们可以先把 $n-x$ 个 $0$ 放入序列，再在 $n-x+1$ 个空隙中放入 $x$ 个 $1$，方案数即为 $\dbinom{n-x+1}{x}$。我们再线性筛出 $i^a$ 和 $i^b$。时间复杂度 $O(n)$。

Anton and School - 2

给定一个长度为 $n$ 的由小括号组成的序列，求有多少子序列满足左半部分为 (，右半部分为 )。

数据范围：$n \le 2\times 10^5$。

---

我们枚举每一个 (，在它左边有 $a$ 个 (（包括它自己），右边有 $b$ 个 )。那么它对答案的贡献为 $\sum \limits _{i=0}^{\min(a-1, b-1)}\dbinom{a-1}{i}\dbinom{b}{i+1}$。我们发现这玩意和范德蒙德卷积 $\sum \limits _{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}$ 差不多。我们考虑化简这个式子。

我们把上面的 $\min$ 拆掉，那么当 $a\le b$ 时

$$\begin{aligned} \sum \limits _{i= 0}^{a-1}\dbinom{a-1}{i}\dbinom{b}{i+1} & = \sum \limits _{i = 0}^{a-1}\dbinom{a-1}{a-1-i}\dbinom{b}{i+1}\\ & = \sum \limits _{i = 0}^{a}\dbinom{a-1}{a-1-i}\dbinom{b}{i+1}\\ & = \dbinom{a+b-1}{a} \end{aligned}$$

当 $b \le a$ 时，

$$\begin{aligned} \sum \limits _{i= 0}^{b-1}\dbinom{a-1}{i}\dbinom{b}{i+1} & = \sum \limits _{i = 0}^{b-1}\dbinom{a-1}{i}\dbinom{b}{b-1-i}\\ & = \dbinom{a+b-1}{b-1}\\ &=\dbinom{a+b-1}{a} \end{aligned}$$

因此对答案的贡献即为 $\dbinom{a+b-1}{a}$。直接 $O(n)$ 即可

梦现时刻

设 $f_{a,b}=\sum \limits _{i=0}^b\dbinom{b}{i}\dbinom{n-i}{a}$，求 $\oplus _{a=1}^m\oplus_{b=1}^m f_{a,b} \bmod 998244353$。

其中 $\oplus$ 为异或运算。

数据范围：$1 \le n \le 10^0, m \le 5000$。

---

比较牛逼的推式子题。

$$\begin{aligned}f_{a,b} & = \sum \limits _{i = 0}^b\dbinom{b}{i}\dbinom{n-i}{a} \\&=\sum \limits _{i=0}^b\dbinom{b-1}{i}\dbinom{n-i}{a}+\sum \limits _{i=0}^b\dbinom{b-1}{i-1}\dbinom{n-i}{a}\\&=f_{a,b-1}+\sum \limits _{i=0}^{b-1}\dbinom{b-1}{i}\dbinom{n-i-1}{a}\\&=f_{a,b-1}+\sum \limits _{i=0}^{b-1}\dbinom{b-1}{i}\dbinom{n-i}{a}-\sum \limits _{i=0}^{b-1}\dbinom{b-1}{i}\dbinom{n-i-1}{a-1}\\&=2f_{a,b-1}-\sum \limits _{i=0}^{b-1}\dbinom{b-1}{i}\dbinom{n-i-1}{a-1}\\&=2f_{a,b-1}-(\sum \limits _{i=0}^{b-1}\dbinom{b}{i+1}\dbinom{n-i-1}{a-1}-\sum \limits _{i=0}^{b-1}\dbinom{b-1}{i+1}\dbinom{n-i-1}{a-1})\\&=2f_{a,b-1}-\sum \limits _{i=0}^{b}\dbinom{b}{i}\dbinom{n-i}{a-1}+\sum \limits _{i=0}^{b}\dbinom{b-1}{i}\dbinom{n-i}{a-1}\\&=2f_{a,b-1}-f_{a-1,b}+f_{a-1,b-1}\end{aligned}$$

直接 $O(n^2)$ 递推。

[AGC002F] Leftmost Ball

给你 $n$ 种颜色的球，每种颜色的球有 $k$ 个，把这 $n\times k$ 个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。

数据范围：$1\leq n, k\leq 2000$。

---

合法的情况为：在任意前缀中，白球的种类都大于等于其他颜色的种类。

设 $f_{i, j}$ 为已经放了 $i$ 个白球和 $j$ 种颜色的方案数。

为了防止方案重复，我们规定，每次放球时，必须将球放到第一个空位上。

考虑最左边的第一个空位放什么球。当放白球时，可以从 $f_{i-1,j}$ 转移过来。

当放其他颜色的球时，可以从 $f_{i, j+1}$ 转移过来。我们考虑这种情况的转移：先从剩余的 $n-j+1$ 种颜色中选出一种，再让一个球放到最左边的空位中，剩下 $k-2$ 个球在剩下的空位中随便放。因此转移方程即为 $f_{i,j}=f_{i-1,j}+f_{i,j-1}\times (n-j+1)\times \dbinom{nk-i-(j-1)(k-1)-1}{k-2}$。

时间复杂度为 $O(n^2)$。

容斥原理 二项式反演

硬币购物

有四种面值为 $c_1,c_2,c_3,c_4$，$T$ 次询问，每次询问给出 $lim_1,lim_2,lim_3,lim_4,tot$，求出在第 $i$ 种硬币不超过 $lim_i$ 的情况下凑出 $tot$ 面值的方案数。

数据范围：$T \le 1000$。

---

先做一遍完全背包，求出没有限制时凑出面值 $t$ 的方案。再用类似多重集组合数的思想，容斥一下把限制消掉，即可得出答案。时间复杂度 $O(16T)$。

[CSP-S2019] Emiya 家今天的饭

有 $n$ 种烹饪方法，$m$ 种主要食材，能用第 $i$ 种烹饪方法和第 $j$ 种食材做出 $a_{i,j}$ 种菜。同时有 3 条限制：做至少一道菜，每道菜烹饪方法互不相同，每种食材至多在一半的菜中被使用。求合法方案数。

数据范围：$n \le 100, m \le 2 \times 10^3$。

---

考虑容斥，让一种菜超出一半的限制，再用总方案减去即可。考虑求出总方案。设 $f_{i, j}$ 为前 $i$ 种菜选 $j$ 种食材的方案数，$s_i$ 为 $\sum_{j=1}^m a_j$。转移即为 $f_{i,j}=f_{i-1,j}+s_i\times f_{i-1,j-1}$，总方案即为 $\sum_{i=1}^n f_{n,i}$。再减去不符合限制的。设当前枚举到的食材为 $p$，设 $g_{i, j, k}$ 表示前 $i$ 个食材中选了 $p$ 这种食材 $j$ 次，其他食材 $k$ 次的方案，根据选不选 $p$ 食材有下面的转移：$g_{i, j, k} = g_{i-1,j,k}+a_{i,p}g_{i-1,j-1,k}+(s_i-a_{i,p})g_{i-1,j,k-1}$，但是这样复杂度为 $O(mn^3)$，考虑优化。注意到我们其实只关心 $j$ 和 $k$ 的相对大小，那我们就设 $g_{i,j}$ 为前 $i$ 个食材中选了 $p$ 这种食材的次数再减去其他食材选的次数为 $j$ 的方案。那么我们就有转移：$g_{i, j} = g_{i-1,j}+a_{i,p}g_{i-1,j-1}+(s_i-a_{i,p})g_{i-1,j+1}$。时间复杂度 $O(mn^2)$。

[HNOI2011] 卡农

从集合 $S=\{ 1, 2, 3\cdots n\}$ 中选出 $m$ 个非空子集，满足所有元素在这些集合中出现的总次数都为偶数，求方案数。

数据范围：$n \le 10^6$。

---

我们可以把题意转化为：有 $2^n-1$ 个二进制数，求从其中选出 $m$ 个数异或为 $0$ 的方案数。我们考虑先求出选择的排列数，最后再除以 $m!$ 即可。我们设 $f_i$ 为从这些数中选出 $i$ 个数的排列使得异或为 $0$ 的方案。总的方案数为 $A_{2^n-1}^{i-1}$，也就是先选出 $i-1$ 个数，这些数异或为 $x$，再将 $x$ 选上，再减去不合法的方案数。考虑有哪些情况是不合法的，第一种是当前选择 $x=0$ 的情况，这时前 $i-1$ 个数已经构成了合法方案，需要减去。再考虑重复的问题，假设 $x$ 与前面选择的数有重复，那么 $x$ 和这个数异或后为 $0$，剩下 $i-2$ 个数也是合法的。$x$ 有 $2^n-1-(i-2)$ 种取值，再考虑第几个数和 $x$ 重复，方案就有 $i-1$ 种。因此总的递推式即为 $f_i=A_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}\times (2^n-i+1)\times (i-1)$。答案就为 $\frac{f_m}{m!}$。

[HAOI2018]染色

有一个长度为 $n$ 的序列，有 $m$ 种颜色给这个序列染色。我们只关心出现次数恰好为 $s$ 的颜色种类。当有 $k$ 种颜色恰好出现了 $s$ 次时，愉悦度为 $w_k$。求所有方案的愉悦度之和模 $1004535809$ 的值。

---

$1004535809$ 为质数，原根为 $3$，常用作 NTT 模数。

我们设 $f_i$ 为恰好出现 $s$ 次的颜色恰好有 $i$ 种的方案数，$g_i$ 为恰好出现 $s$ 次的颜色至少有 $i$ 种的方案数。我们考虑先求出 $g_i$。我们先从 $m$ 种颜色中选出 $i$ 种颜色，再考虑在序列中如何放置这些颜色。我们把空着的 $n-is$ 位置都看成相同的颜色，这就是一个多重集组合数，方案为 $\frac{n!}{(s!)^i(n-is)!}$。再把剩下的 $m-i$ 种颜色放到剩下 $n-is$ 个位置上，方案数为 $(m-i)^{n-is}$。因此 $g_i=\dbinom{m}{i} \frac{n!}{(s!)^i(n-is)!} (m-i)^{n-is}$。

再考虑求出 $f_k$。设 $up = \min(m,\left \lfloor \frac{n}{s} \right \rfloor)$

$$\begin{aligned} f_k & = \sum \limits _{i = k}^{up}(-1)^{i-k}\dbinom{i}{k}g_i\\ &= \sum \limits _{i = k}^{up}\frac{(-1)^{i-k}i!}{(i-k)!k!} g_i\\ &=\frac{1}{k!} \sum \limits _{i = k}^{up}\frac{(-1)^{i-k}}{(i-k)!}(i!g_i) \end{aligned}$$

设 $F(x)=\sum \limits_{i=0}^{up}\frac{(-1)^i}{i!}x^i,G(x)=\sum \limits_{i=0}^{up}i!\times g_i\times x^i$。则 $f_k=\frac{1}{k!} \sum \limits_{i=k}^{up}F_{i-k}G_{i}$。这就是一个常见的差卷积形式，翻转一下即可转变为和卷积形式，直接 NTT 即可。时间复杂度 $O(m\log m)$。

[JSOI2011]分特产

有 $m$ 种不同的特产，每种特产有 $a_i$ 个，要把这些特产分给 $n$ 个人，要求每个人必须有至少一件特产，求方案数。

数据范围：$n, m, a_i \le 1000$。

---

设 $g_i$ 为至少 $i$ 个人没有特产的方案数，先选出没有拿到特产的人，再把剩下的特产每种分别分给剩下的人，直接插板法即可，则 $g_i=\dbinom{n}{i} \prod_{j=1}^{m}\dbinom{a_j+n-i-1}{n-i-1}$。最后二项式反演 $ans = \sum_{i=0}^n (-1)^i g_i$。时间复杂度 $O(nm)$。

[TJOI2019]唱、跳、rap和篮球

现在有 $a$ 个 A，$b$ 个 B，$c$ 个 C，$d$ 个 D，要求把这些字母中的 $n$ 个填到长度为 $n$ 的序列中，要求序列中不能按顺序出现相邻的 ABCD。求合法方案数对 $998244353$ 取模的值。

数据范围：$n \le 1000, a,b,c,d \le 500$。

---

考虑二项式反演，设 $g_i$ 为序列中至少出现了 $i$ 个 ABCD 的方案，我们先把这 $i$ 个位置填上，再在剩下 $n-4i$ 个位置多重集组合数下，就可以求出 $g_i$。考虑写出 $g_i$ 的表达式，设 $h_{n,a,b,c,d}$ 为有 $a$ 个 A，$b$ 个 B，$c$ 个 C，$d$ 个 D 的情况下在 $n$ 个位置中随便放的方案数，则 $g_i=\dbinom{n-3i}{i}h_{n-4i,a-i,b-i,c-i,d-i}$。再考虑求出 $h$。根据多重集组合数，$h_{n,a,b,c,d}=\sum\limits_{p=0}^a\sum\limits_{q=0}^b\sum\limits_{s=0}^c\sum\limits_{t=0}^d \frac{n!}{p!q!s!t!}[p+q+s+t=n]$，这就是一个卷积形式了，直接 NTT 即可。时间复杂度 $O(n^2\log n)$。

[ARC160D] Mahjong

统计满足经过以下两种操作可以使得元素全为 $0$ 的长度为 $n$，元素和为 $m$ 的 $A$ 序列的个数：1. 选取一个元素使其减去 $k$。2. 选取长度为 $k$ 的子串，使其全部都减去 $1$。

数据范围：$k, n \le 2000, m \le 10^{18}$。

---

有意思的计数题。注意到无解当且仅当 $k\not\mid m$。再考虑有解如何统计。我们可以把操作也看成一个序列 $B$，$B$ 序列的长度为 $2n-k+1$，$B$ 序列的前 $n$ 个数代表的是第一种操作。$B_i=p$ 就意味着在 $i$ 这个位置进行了 $p$ 次 $1$ 操作。$B$ 序列的后 $n-k+1$ 个数表示的是第二种操作，$B_{i+n}=p$ 就意味着在以 $i$ 开头的子串中进行了 $p$ 次操作。同时为了防止重复，我们规定 $B_i < k(n < i \le 2n - k + 1)$。这样我们就能建立起操作和原序列的一一对应关系了。我们再考虑 $B$ 序列的计数。首先 $\sum _{i=1}^{2n-k+1}B_i=\frac{m}{k}$，其中只有后面的 $B_i$ 是有限制的，这就转化成了多重集组合数问题，直接容斥。设 $g_i$ 为至少有 $i$ 个 $B_i$ 不满足限制的方案数，先选出哪些位置不满足要求，然后直接插板即可，因此 $g_i=\dbinom{n-k+1}{i}\dbinom{\frac{m}{k}-i\times k+2n-k}{2n-k}$。最后二项式反演即可得出答案。

[ABC214G] Three Permutations

给定长度为 $n$ 的两个排列 $p, q$，求满足 $\forall i \in [1,n],r_i\not= p_i,r_i\not=q_i$ 的 $r$ 排列的方案数。

数据范围：$n \le 3000$。

---

考虑二项式反演，求出至少有 $i$ 个限制不满足的方案 $h_i$。我们从 $p_i$ 向 $q_i$ 连边，这时我们把这条边称作第 $i$ 条边，第 $i$ 个限制不满足就等价于第 $i$ 条边对应它的起点或终点。把这些边都连上之后会形成一些环，我们把没有对应自己起点或终点的边删去。我们先考虑一个环，设 $dp_{i, j}$ 为把长度为 $i$ 的链删去 $j$ 条边之后对应的方案数，易知大小为 $i$ 的链对应的方案数为 $i$，则 $dp_{n,m}=\sum_{i=1}^n idp_{n-i,m-1}$。再考虑环，设 $f_{i,j}$ 为把大小为 $i$ 的环删去 $j$ 条边之后对应的方案数，则 $f_{n, m} = \sum_{i=1}^n i^2 f_{n-i, m-1}$。再考虑所有的环，设 $g_{i, j}$ 为前 $i$ 个环共删去 $j$ 条边的对应方案数，则 $g_{n, m}=\sum_{i=1}^{v_{n}} g_{n-1, m}f_{v_n, i}$。最后 $h_i$ 就等于 $g_{cnt, n-i}$。

随机立方体

有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。

数据范围：$n, m, l \le 5\times 10^6, k\le 100$。

---

看到恰好，直接二项式反演。我们只需要考虑至少有 $k$ 个极大的数的情况。我们把这种情况的方案数记作 $f(k)$。考虑如何求出 $f(i)$。

我们钦定完这 $i$ 个数后，剩下的 $(n-i)(m-i)(l-i)$ 个位置都是可以随便放置的。然后我们再按顺序选择出来这 $i$ 个坐标不相同的数。总的方案数我们可以写作：

$$f_i=(n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})\left ( (nml)^{\underline{(n-i)(m-i)(l-i)}}\right )g_i$$

第一项为选择这 $i$ 个坐标不同的数，第二项为放置剩下的位置，第三项为被这些极大点所限制的数的填法。我们再考虑求出 $g_i$。

由于每个点可能会受到多个极大点的限制，因此我们需要从大到小来考虑填数，因为小的极大点的限制更强。我们结合下面这张图来推式子。

在图中，粉色部分为无限制区域，一半红的是放了关键点的区域，与关键点另一半相同颜色的区域是受该关键点控制的区域（这里为了方便，将关键点从左上到右下按从大到小排序）。这时我们可以计算一下：$g(3)=29^{\underline{7}}\times 21^{\underline{9}}\times 11^{\underline{11}}$。

因此我们可以得到 $g_i$ 的公式：

设 $h(x)=(n-x)(m-x)(l-x)$，则

$$\begin{aligned} g_i&=\prod_{j=1}^{i}(h(0)-h(j)-1)^{\underline{h(j-1)-h(j)-1}}\\ &=\prod _{j=1}^i \frac{(h(0)-h(j)-1)!}{(h(0)-h(j-1))!} \\ &=(h(0)-h(i)-1)!\prod_{j=1}^{i-1} \frac{1}{(h(0)-h(j))!} \end{aligned}$$

再带回 $f_i$ 中，即可得到：

$$\begin{aligned} f_i & = (n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})\left ( (nml)^{\underline{(n-i)(m-i)(l-i)}}\right )g_i\\ &=(n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})\left ( (nml)^{\underline{(n-i)(m-i)(l-i)}}\right )(h(0)-h(i)-1)!\prod_{j=1}^{i-1} \frac{1}{(h(0)-h(j))!}\\ &=(n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})\frac{(nml)!}{(nml-h(i))}(nml-h(i)-1)!\prod_{j=1}^{i-1}\frac{1}{nml-h(j)} \\ &=(n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})(nml)!\prod_{j=1}^{i}\frac{1}{nml-h(j)} \\ \end{aligned}$$

由于最终还要除掉 $(nml)!$，则我们直接把它去掉。

$$\begin{aligned} f(i)&=(n^{\underline{i}}m^{\underline{i}}l^{\underline{i}})\prod_{j=1}^{i}\frac{1}{nml-h(j)} \\ ans&=\sum \limits _{i=k}(-1)^{i-k}\dbinom{i}{k}f(i) \end{aligned}$$

Ban Permutation

问长度为 $n$，且 $\forall i, |i-p_i|\ge X$ 的排列的数量。

数据范围：$n\le 100, X \le 5$。

---

我们先用二项式反演将题目的限制变为 $|i-p_i|<X$。我们考虑钦定 $i$ 个位置满足的方案。

我们设 $g_{i, j, s}$ 为用前 $i$ 个数，已经钦定了 $j$ 个数，并且 $[i-X+1, i+X-1]$ 这段区间的占用情况为 $s$ 时的方案数。转移就按照是否钦定当前数来转移。具体的说：

$$g_{i, j, T}=g_{i-1,j,s}+\sum g_{i-1, j-1, s'}$$

这样就能求出钦定 $i$ 个数时的方案数，二项式反演即可得到结果。

时间复杂度 $O(4^Xn^2)$

Lamps and Buttons

有 $n$ 盏灯，其中前 $m$ 盏灯是亮着的。现在随机生成一个排列 $p$，第 $i$ 个开关能被按下当且仅当第 $i$ 盏灯亮着，按下第 $i$ 个开关会使得第 $p_i$ 盏灯的状态改变。现在一个人来按开关，这个人不知道 $p$ 排列。当所有灯亮起时他赢，如果无法操作时他输。假设这个人绝顶聪明，问对于所有的排列 $p$，这个人的胜率之和。

数据范围：$n \le 10^7, m\le 5000$。

---

我们把 $i$ 和 $p_i$ 连边。我们先考虑什么情况会输：按到自环或者在没亮的灯中出现了环。这样无论如何也无法使得所有灯亮起来。由于这个人不知道排列 $p$，因此他最好的顺序就是没有顺序，从左往右按就完事了。我们的问题就转化为了：把灯从左往右按，在碰到第一个自环前把所有的灯按亮的方案数。

我们枚举第一个自环的位置 $i$，我们发现在它前面没有自环的方案数很难求，我们可以用二项式反演求出在它前面有 $x$ 个自环的方案数，同时我们还要满足后面 $n-m$ 个数都能包在前面的环中。我们可以让后面这些数插入到前面 $i-x$ 个位置所成的环中，因此总方案数为（下面的公式中 $a=i-x-1, b = n-m, c = m-i$：

$$1\times 2\times \cdots \times a\times a\times (a+1)\times \cdots \times (a+b-1)\times (a+b+1)\times \cdots(a+b+c)=\frac{a(a+b+c)}{(a+b)}$$

总时间复杂度 $O(n+m^2)$。

成绩比较

G 系共有 $n$ 位同学，$m$ 门必修课。这 $n$ 位同学的编号为 $0$ 到 $n-1$ 的整数，其中 B 神的编号为 $0$ 号。这 $m$ 门必修课编号为 $0$ 到 $m-1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $u_i$ 中的一个整数。

如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。在 B 神的说法中，G 系共有 $k$ 位同学被他碾压（不包括他自己），而其他 $n-k-1$ 位同学则没有被他碾压。D 神查到了 B 神每门必修课的排名 $r_i$。

求出全系所有同学每门必修课得分的情况数，使其既能满足 B 神的说法，也能符合 D 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

数据范围：$n, m, r_i\le 100, u_i\le 10^9$。

---

首先我们发现恰好 $k$ 这个条件不太好搞，我们就可以用二项式反演来把它搞掉。

我们设 $g_i$ 为至少 $i$ 个人被碾压的方案数，我们就可以得到最终的答案为：

$$ans=\sum\limits_{i=k}^{n-1}\dbinom{i}{k}(-1)^{i-k}g_i$$

我们现在就考虑如何求出 $g_i$。我们对于每一科分开考虑，先选出 $i$ 个人被碾压，然后再从剩下的 $n-1-i$ 人中选出分数比他低的剩下 $n-r_i-i$ 个人。最后再枚举他的分数，将两拨人分开放即可。

因此我们最终出来的式子是：

$$g_i=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j} k^{n-r_j}(u_j-k)^{r_j-1}$$

然后我们发现最后的 $\sum$ 很难求，因为 $u$ 的范围太大。我们尝试化一下式子。

$$\begin{aligned} g_i&=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j} k^{n-r_j}(u_j-k)^{r_j-1}\\ &=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j}k^{n-r_j}\sum\limits_{l=0}^{r_j-1}\dbinom{r_j-1}{l}(-k)^l u_j^{r_j-1-l}\\ &=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{l=0}^{r_j-1}\dbinom{r_j-1}{l}u_j^{r_j-1-l}(-1)^l\sum\limits_{k=1}^{u_j}k^{n-r_j+l} \end{aligned}$$

我们发现最后的 $\sum\limits_{k=1}^{u_j}k^{n-r_j+l}$ 是可以直接 $O(n)$ 插出来的，因此就可以解决了。

时间复杂度 $O(n^3)$

Natasha, Sasha and the Prefix Sums

一个长度为 $n+m$，有 $n$ 个 $1$ 和 $m$ 个 $-1$ 的序列 $a$，定义其最大前缀和为： $\max\{ 0,\max\limits_{1\le i\le n+m}\sum\limits_{j=1}^ia_j \}$

求出对于全部可能的序列，它们的最大前缀和之和是多少。

$0\le n,m \le 2000$

---

我们可以把放入 $1$ 和 $-1$ 转化为格路，我们设 $1$ 为向上走，$-1$ 为向下走，我们对应到坐标系中最后一定会走到 $(m, n)$ 这个点。我们考虑它的最大前缀和是什么。

如果一条折线能顶到的最高的直线为 $y=x+k$，那么它的最大前缀和即为 $k$。我们可以看下图来理解：

这样的一条路径对应的序列就是 -1 -1 1 1 1 -1 1 -1 -1 -1 -1，显然它的最大前缀和就是 $1$，也恰好对应了 $y=x+1$ 这条折线。

因此我们现在要计算的就是对于每一条 $y=x+k$，恰好顶到它的折线数量。这个数量再乘上 $k$ 即为它的贡献。

我们可以考虑容斥，我们用经过 $y=x+k$ 的折线数量减去 $y=x+k+1$ 的折线数量，就是恰好顶到 $y=x+k$ 的数量。而对于经过 $y=x+k$ 直线的折线的数量，我们可以类似卡特兰数的方法，从第一次接触的地方对称，即可得到方案数为 $\dbinom{n+m}{n-k}$。

这样枚举每一条 $y=x+k$ 即可算出答案。

时间复杂度 $O(n)$。

博弈论与概率统计

Alice 和 Bob 在玩一个双人游戏。每一轮中，Alice 有 $p$ 的概率胜利，$1-p$ 的概率失败，不会出现平局。

双方初始时各有 $0$ 分，当一个人胜利的时候，他会获得一分，失败则扣掉一分。但是如果某个人输掉一轮比赛的时候他只有 $0$ 分，那么他就不会被扣分（对方会照常加一分）。多次询问，每次给定 $n, m$，表示游戏一共要进行 $n+m$ 轮，其中 Alice 恰好赢了 $n$ 轮，算出在游戏结束时 Alice 的得分的数学期望。

数据范围：$n+m, q\le 2.5\times 10^5$。

---

首先题目中的 $p$ 没有用，最终求个总得分除去总方案数就行了。我们可以把整个输赢序列看作在二维平面上走，输则往上走，赢则往下走。这样总的方案数即为 $\dbinom{n+m}{n}$。

我们考虑总得分如何计算。我们先假设没有减到 $0$ 则不减少的机制，把整场比赛的分数情况画出来，应该是这样的：

但是我们有了保护机制，因此折线应该是这样的：

最终得分会增加遇到的最低的线，转化到上面的那个网格图中即为：一条折线与 $y=x+b$ 从上面最先接触，那么该折线的得分会增加 $b$。而我们通过容斥可以得到：和 $y=x+b$ 从上面最先接触的折线的数量为穿过 $y=x+b-1$ 且不穿过 $y=x+b$ 的折线数量，这两个都能用卡特兰数类似的方法对称得出。因此和 $y=x+b$ 从上面最先接触的折线的数量为：$\dbinom{n+m}{n+b-1} - \dbinom{n+m}{n+b}$

这样我们就能列出下面的式子：

$$\begin{aligned} ans & = \sum \limits_{i = 0}^{m} \left ( \dbinom{n+m}{n+i}-\dbinom{n+m}{n+i+1} \right )(n-m+i)\\ &=(n-m)\dbinom{n+m}{n}+\sum \limits_{i=0}^{m-1}\dbinom{n+m}{i} \end{aligned}$$

这里我们只考虑了 $n\ge m$ 的情况，对于 $n<m$ 的情况也能同理推出类似的式子。现在我们只需要维护后面这个玩意：$\sum \limits_{i=0}^{m-1}\dbinom{n+m}{i}$。

我们这里可以考虑莫队，我们设 $f(l, r)=\sum \limits_{i=0}^{r}\dbinom{l}{i}$，我们可以发现 $l, r$ 扩展都是 $O(1)$ 的，因此我们就可以把所有询问离线下来，进行莫队统一处理。

因此时间复杂度 $O(n\sqrt n)$。

推式子

Team Work

给定 $n,k$，求：$\sum_{i=1}^n\binom n i \times i^k$

数据范围：$1 \leq k \leq 5000,1 \leq n \leq 10^9$。

---

$$\begin{aligned} \sum \limits_{i=1}^n \dbinom{n}{i}i^k&=\sum \limits _{i=0}^n\dbinom{n}{i}\sum \limits _{j=0}^k {k\brace j}\dbinom{i}{j}j!\\ &=\sum \limits _{j=0}^k{k \brace j}j!\sum \limits_{i=0}^n\dbinom{n}{i}\dbinom{i}{j}\\ &= \sum \limits _{j=0}^k{k\brace j}j!\sum \limits _{i=0}^n\dbinom{n}{j}\dbinom{n-j}{i-j}\\ &=\sum \limits _{j=0}^k{k\brace j}j!\dbinom{n}{j}\sum \limits_{i=0}^n\dbinom{n-j}{i-j}\\ &=\sum \limits _{j=0}^k {k\brace j} \frac{n!}{(n-j)!}2^{n-j} \end{aligned}$$

直接 $O(n^2)$ 递推斯特林数即可。

[HEOI2016/TJOI2016]求和

求 $\sum \limits _{i=0}^n\sum \limits _{j=0}^i{i\brace j}2^j\times j!$。

数据范围：$n \le 10^5$。

---

$$\begin{aligned} \sum \limits _{i = 0}^n\sum \limits _{j = 0}^i{i\brace j}2^j\times j!&=\sum \limits _{j=0}^n2^jj!\sum \limits _{i=0}^n{i\brace j}\\ &=\sum \limits _{j=0}^n2^jj!\sum \limits _{i=0}^n\sum \limits _{k=0}^j\frac{(-1)^{j-k}k^i}{k!(j-k)!}\\ &=\sum \limits _{j=0}^n2^jj!\sum \limits _{k=0}^j\frac{(-1)^{j-k}}{k!(j-k)!}\sum \limits _{i=0}^n k^i\\ &= \sum \limits _{j=0}^n2^jj!\sum \limits _{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}\frac{(k^{n+1}-1)}{(k!)(k-1)} \end{aligned}$$

推出卷积形式直接 NTT 即可。

[国家集训队] Crash 的文明世界

给定一棵树，对于每个点 $i$，求出 $\sum \limits _{j=1}^ndist_{i,j}^k$。

数据范围：$n \le 50000, k \le 150$。

---

$$\begin{aligned} \sum \limits _{i = 1}^ndist_{u, i}^k &= \sum \limits _{i=1}^n\sum \limits _{j=0}^k{k\brace j}j!\dbinom{dist_{u,i}}{j}\\ &=\sum \limits _{j=0}^k {k\brace j}j!\sum \limits _{i=1}^n\dbinom{dist_{u,i}}{j}\\ \end{aligned}$$

因此我们只需要求出对于每个点的 $\sum \limits _{i=1}^n\dbinom{dist_{u,i}}{j}$，就可求出答案。考虑树上 dp，设 $ans_{u, j}$ 为 $u$ 子树内 $\dbinom{dist_{u,i}}{j}$ 之和，考虑 $\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$，那么 $ans_{u,j}=\sum \limits _{v\in son_u}ans_{v, j}+ans_{v, j-1}$。最后换根 dp 就可以求出所有点的答案了。

CF1278F Cards

有 $m$ 张牌，其中有一张为王牌。现在执行 $n$ 次洗牌后选出最上面的一张牌的操作。设 $x$ 为第一张为王牌的次数，求 $x^k$ 的期望值。

数据范围：$n, m< 998244353, k \le 5000$。

---

$$\begin{aligned}ans &= \sum \limits_{i=0}^n\dbinom{n}{i}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}i^k\\ &=\sum\limits_{i=0}^n\dbinom{n}{i}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}\sum\limits _{j=0}^k\dbinom{i}{j}j!{k\brace j}\\&=\frac{1}{m^n}\sum \limits_{j=0}^k{k\brace j}j!\sum \limits _{i=0}^n(m-1)^{n-i}\dbinom{n}{i}\dbinom{i}{j}\\&= \frac{1}{m^n}\sum \limits_{j=0}^k{k\brace j}j!\sum \limits _{i=0}^n(m-1)^{n-i}\dbinom{n}{j}\dbinom{n-j}{i-j}\\&=\frac{1}{m^n}\sum \limits_{j=0}^k{k\brace j}j!\dbinom{n}{j}\sum\limits_{i=0}^{n-j}\dbinom{n-j}{i}(m-1)^{n-i-j}\times 1^{i}\\&=\frac{1}{m^n}\sum \limits_{j=0}^k{k \brace j}j!\dbinom{n}{j}m^{n-j}\\&= \sum \limits_{j=0}^k{k \brace j}\frac{n!}{(n-j)!} \times \frac{1}{m^j} \end{aligned}$$

$O(n^2)$ 递推即可。

Partitions

有 $n$ 个物品，每个物品有一个权值 $w_i$。一个集合的权值为该集合的大小再乘上其内部物品的权值和，即 $W(S)=|S|\sum w_i$。一个划分的权值为所有集合的权值和。求 $n$ 个物品划分成 $k$ 个集合的所有方案的权值和。

数据范围：$n, k \le 2\times 10^5$。

---

易知每个物品在所有划分方案中贡献的次数是相同的，记为 $cnt$，开始推式子。

$$\begin{aligned} cnt &= \sum\limits_{s=1}^n(s\times \dbinom{n-1}{s-1}\times {n-s\brace k-1})\\ &=\sum \limits_{s=1}^ns\dbinom{n-1}{s-1}\sum \limits_{i=0}^{k-1}\frac{(-1)^i(k-1-i)^{n-s}}{i!(k-1-i)!}\\ &=\sum\limits _{i=1}^{k-1}\frac{(-1)^i}{i!(k-1-i)!}\sum \limits _{s=1}^ns\dbinom{n-1}{s-1}(k-1-i)^{n-s} \end{aligned}$$

我们再单独考虑后面的和式。

有一个公式 $m\dbinom{n}{m}=n\dbinom{n-1}{m-1}$

$$\begin{aligned} tmp&=\sum \limits_{s=1}^n\dbinom{n-1}{s-1}(k-1-i)^{n-s}+\sum \limits _{s=1}^n(s-1)\dbinom{n-1}{s-1}(k-1-i)^{n-s}\\ &=\sum \limits_{s=1}^n\dbinom{n-1}{s-1}(k-1-i)^{n-s}+(n-1)\sum \limits _{s=1}^n\dbinom{n-2}{s-2}(k-1-i)^{n-s}\\ \end{aligned}$$

然后二项式定理即可。

$$\begin{aligned} tmp&=(k-i)^{n-1}+(n-1)(k-i)^{n-2}\\ &=(k-i)^{n-2}(k-i+n-1) \end{aligned}$$

因此最终答案为 $\sum\limits _{i=1}^{k-1}\frac{(-1)^i(k-i)^{n-2}(k-i+n-1)}{i!(k-1-i)!}$。

[省选联考 2020 A 卷] 组合数问题

给定一个 $m$ 次多项式 $f(x)=a_0+a_1x+\cdots +a_mx^m$，求 $\sum \limits_{k=0}^nf(k)\times x^k\times \dbinom{n}{k}$。

数据范围：$n \le 10^9, m \le 1000$。

---

本题要用新科技：下降幂。本来不想写这题的发现有不会的新科技才写的

我们先把 $f(x)$ 转化为下降幂多项式 $f(x)=b_0+b_1x+\cdots b_m x^{\underline{m}}$，再开始推式子。

$$\begin{aligned} \sum \limits _{i = 0}^nf(i)x^i\dbinom{n}{i} &=\sum \limits_{i=0}^n\sum \limits _{j=0}^mb_j\times i^{\underline{j}}\dbinom{n}{i}x^i\\ &= \sum \limits_{i=0}^n\sum \limits _{j=0}^mb_j\times n^{\underline{j}}\dbinom{n-j}{i-j}x^i\\ &=\sum \limits_{i=0}^nx^i\sum \limits _{j=0}^mb_j\times n^{\underline{j}}\dbinom{n-j}{i-j}\\ &=\sum \limits_{j=0}^mb_jn^{\underline{j}}\sum \limits_{i=0}^n\dbinom{n-j}{i-j}x^i\\ &= \sum \limits_{j=0}^mb_jn^{\underline{j}}\sum \limits_{i=0}^{n-j}\dbinom{n-j}{i}x^{i+j}\\ &=\sum \limits_{j=0}^mb_jn^{\underline{j}}x^j\sum \limits_{i=0}^{n-j}\dbinom{n-j}{i}x^{i}\\ &=\sum \limits_{j=0}^mb_jn^{\underline{j}}x^j(x+1)^{n-j} \end{aligned}$$

再回顾一开始普通幂转下降幂的式子，则有

$$\sum\limits_{i=0}^ma_ix^i=\sum \limits_{i=0}^ma_i\sum \limits _{j=0}^i{i\brace j}x^{\underline{j}}=\sum \limits_{i=0}^mx^{\underline{i}}\sum \limits _{j=i}^m{j\brace i}a_j$$

因此 $b_j=\sum \limits _{j=i}^m{j\brace i}a_j$。直接 $O(n^2)$ 递推即可。

The End

组合数学博客也肝了一段时间了，从开始做到肝完博客也花了十天左右，以后可能还会加点有意思的组合数学题（也感觉自己数数能力好了点）。