本篇文章是为了总结一下最近做的组合数学的题目以及涉及到的知识点，以后可能会不定期补充。同时也参考了大佬 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}\)。

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

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

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

大小为 \(n\) 的二叉树数量。
凸 \(n+2\) 边形的三角剖分数量。
\(n\) 个元素进栈出栈的排列数量。
从 \((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}\)。

推式子

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-1)\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)\) 递推即可。