组合数学

Published: August 21, 2019 by Daltao

• Categories:
• math 2

• Tags:

• 几类组合数加总的计算方式
  • 类型1
  • 类型2
  • 类型3
• 非连续0问题
• 统计选球方案
• 统计所有和方案数问题
• 错位排序的一些问题
• 递增序列方案数
• 生成函数
• 网格问题
• 统计多重集合
• Hockey Stick Identity
• 参考资料

几类组合数加总的计算方式

类型1

对于所有$k=0,1,2,\ldots,n$，要求计算：

$$f(k)=\sum_{i=0}^nc_i{k\choose i}$$

很显然存在$O(n^2)$的算法，但是这太慢了，下面我们利用多项式进行加速计算。

$$f(k)=\sum_{i=0}^nc_i{k\choose i}\\ =\sum_{i=0}^nc_i\frac{k!}{i!(k-i)!}\\ =k!\sum_{i=0}^n\frac{c_i}{i!}\frac{1}{(k-i)!}\\$$

其中$\sum_{i=0}^n\frac{c_i}{i!}\frac{1}{(k-i)!}$可以表示为下面两个函数的卷积

$$A(x)=\sum_{i=0}^n\frac{c_i}{i!}x^i\\ B(x)=\sum_{i=0}^n\frac{1}{i!}x^i$$

利用快速卷积可以在$O(n\log_2n)$的时间复杂度内实现。记$C(x)=A(x)\times B(x)$，那么$f(k)=k!C_k$

类型2

对于所有$k=0,1,2,\ldots,n$，要求计算：

$$f(k)=\sum_{i=0}^nc_i{i\choose k}$$

很显然存在$O(n^2)$的算法，但是这太慢了，下面我们利用多项式进行加速计算。

$$\begin{aligned} f(k)&=\sum_{i=0}^nc_i{i\choose k}\\ &=\sum_{i=0}^nc_i\frac{i!}{k!(i-k)!}\\ &=\frac{1}{k!}\sum_{i=0}^nc_ii!\frac{1}{(i-k)!} \end{aligned}$$

其中右边部分$\sum_{i=0}^nc_ii!\frac{1}{(i-k)!}$是等差卷积，即令

$$A(x)=\sum_{i=0}^nc_{n-i}(n-i)!x^i\\ B(x)=\sum_{i=0}^ni!x^i$$

令$C(x)=A(x)\times B(x)$

那么有$f(k)=\frac{1}{k!}C_{n-k}$

利用快速卷积算法我们可以在$O(n\log_2n)$的时间复杂度内计算出所有结果。

类型3

统计：

$$\sum_{i=0}^a\sum_{j=0}^b{n \choose i}{n - i\choose j}$$

其中$a+b + 1\geq n$。

先来考虑其组合意义，这个问题等价于，有一个序列，取值范围为0~2。我们希望0出现的次数不会超过a，1出现的次数不会超过b。问有多少这样的序列。

我们可以用容斥来解决，问题变成四个：

• 总共有多少个序列（$3^n$)
• 0出现a次以上的序列数
• 1出现b次以上的序列数
• 0、1各出现a、b次以上的次数（0）

因此我们只需要解决第二个和第三个问题，比如第二个问题：

$$\sum_{i=a+1}^n{n\choose i}2^{n-i}$$

这只是一趟循环，第三个问题同。整个时间复杂度为$O(n)$。

如果不能保证$a+b+1\geq n$，那么我们可以将问题现在转换为类型1，之后求解，时间复杂度为$O(n\log_2n)$。

非连续0问题

形式1：对于一个包含k个1的二进制序列，如果没有任意两个0相邻，且第一个数一定是0，那么称该序列为良好的。问，对于所有长度为n的二进制序列，其中有多少是良好的。

这个问题不是很难，我们可以直接用动态规划进行解决。但是除了动态规划，组合数学能提供一种更加简单快捷的解决方案。

这个问题实际上等价于，有两种子序列：

• 10
• 1

我们希望用k个上面子序列来，来组成一个长度为n-1的二进制序列。通过方程组可以简单地推出10序列出现的次数a和1出现的次数b。

$$\left\{ \begin{array}{lll} a+b & = & k\\ 2a+b & = & n-1 \end{array} \right.$$

之后我们进行多重排列的计算就可以得出总的数目了，结果是$\frac{k!}{a!b!}$。

下面我们修改一下原来问题：

形式2：对于一个包含k个1的二进制序列，如果没有任意两个0相邻，且第一个数一定是1，那么称该序列为良好的。问，对于所有长度为n的二进制序列，其中有多少是良好的。

这个问题实际上比上一个问题还要简单，用同样的理论，只是方程组稍微变动一下：

$$\left\{ \begin{array}{lll} a+b & = & k\\ 2a+b & = & n \end{array} \right.$$

形式3：对于一个包含k个1的二进制序列，如果没有任意两个0相邻，且第n个数一定是1（0），那么称该序列为良好的。问，对于所有长度为n的二进制序列，其中有多少是良好的。

直接翻转一下二进制序列，计算完成后翻转回去即可。

形式4：对于一个包含k个1的二进制序列，如果没有任意两个0相邻，且第1个数和第n个数一定是0，那么称该序列为良好的。问，对于所有长度为n的二进制序列，其中有多少是良好的。

先考虑第一个数为0的所有良好序列，其中一部分的尾部是0，其余的则是1。为0表示10子串进行结尾的，因此修改方程组即可。

$$\left\{ \begin{array}{lll} a+b & = & k-1\\ 2a+b & = & n-3 \end{array} \right.$$

统计选球方案

问题1：有n个球，m种颜色。其中第i种颜色的球有$a_i$个。我们现在希望从所有球中挑选$k$个球，问有多少种选取方案。$n,m\leq 10^5$。

考虑从n个球种挑选若干个球的方案。仅考虑颜色为$i$的球，其挑选方案的生成函数为$f_i(x)=x^{a_1}+x^{a_1-1}+\ldots+x^1+1$。当有m种球时，颜色的生成函数为$f(x)=\prod_{i=1}^mf_i(x)$。

我们可以用快速卷积+分治来计算，总的时间复杂度为$O(n\log_2m\log_2n)$。

问题2：有m种颜色，每种颜色的球都有无数个，现在从中取出n个球（两种取法不同当且仅当存在某种颜色，该种颜色的球的数目在两种方案中不同），问有多少种取法。$n,m\leq 10^5$。

记$x_i$表示取出的第$i$种颜色的球的数目，那么有$x_1+x_2+\ldots+x_m=n$且$x_i\geq 0$。取法的数目通过隔板法可以直接得出${m+n-1\choose n-1}$。

问题3：有m种颜色，每种颜色的球都有无数个，现在从中取出n个球（两种取法不同当且仅当存在某种颜色，该种颜色的球的数目在两种方案中不同），问每种颜色的球都至少取出一个的前提下有多少种取法。

记$x_i$表示取出的第$i$种颜色的球的数目，那么有$x_1+x_2+\ldots+x_m=n$且$x_i\geq 1$。取法的数目通过隔板法可以直接得出${m-n+n-1\choose n-1}$。

问题4：有m种颜色，每种颜色的球都有无数个，现在从中取出n个球（两种取法不同当且仅当存在某种颜色，该种颜色的球的数目在两种方案中不同），问每种颜色的球取出数目不超过$k$的前提下有多少种取法。$n,m\leq 10^5$。

这个可以用容斥进行解决。记录$A_i$表示第$i$种颜色出现不超过$k$次的所有方案的集合。那么结果为：

$$|A_1\cap A_2\cap \ldots\cap A_n|=\sum_{i=0}^m(-1)^i{m-(k+1)i+n-1 \choose n-1}$$

问题5：有m种颜色，每种颜色的球有$R$个。现在从中取出n个球（两种取法不同当且仅当存在某种颜色，该种颜色的球的数目在两种方案中不同），要求每种颜色的球至少被取出$L$个，问有多少种取法。$n,m\leq 10^5$。

首先我们可以消除左边界带来的影响，那么问题就变成了$x_1+\ldots +x_m=n$，且$x_i\leq R$。这个可以用容斥来处理。我们定义$C_i$表示所有满足$x_i>R$的方案组成的集合。那么问题的解就是：

$$|\overline{C_1}\cap \overline{C_2}\cap \ldots \cap \overline{C_n}|\\ =\sum_{i=0}^m(-1)^i{m \choose i}{n-i(R+1)+m-1\choose m - 1}$$

问题6：有m种颜色，每种颜色的球都有无数个，现在从中依次取出n个球（两种取法当且仅当两种取法得到的颜色序列不同），问有多少种取法。$n,m\leq 10^5$。

这个问题非常容易，每次取的时候有$m$种可能，因此结果为$m^n$。

问题7：有m种颜色，每种颜色的球都有无数个，现在从中依次取出n个球（两种取法当且仅当两种取法得到的颜色序列不同），且要求每种颜色的球都至少被取出一个，问有多少种取法。$n,m\leq 10^5$。

这个可以用容斥进行解决。记录$A_i$表示第$i$种颜色出现的所有方案的集合。那么结果为：

$$|A_1\cap A_2\cap \ldots\cap A_n|=\sum_{i=0}^m(-1)^i{m \choose i}(m-i)^n$$

问题8：有m种颜色，每种颜色的球都有无数个，现在从中依次取出n个球（两种取法当且仅当两种取法得到的颜色序列不同），且要求第$i$种颜色的球出现的次数$x_i$满足$L_i\leq x_i\leq R_i$，问有多少种取法。$n,m\leq 500$,$L_i\leq R_i \leq 500$。

用动态规划解决。记录$dp(i,j)$表示前$i$种颜色选择$j$个球的方案数。这里没有考虑到排列带来的影响，因此$dp(i-1,j)$对$dp(i,j+t)$的贡献应该为$dp(i-1,j){j+t\choose t}$。

这个问题还可以通过卷积来做，只是比较复杂一些。

统计所有和方案数问题

考虑有n个未知数$x_1,x_2,\ldots, x_n$，其中每个未知数$x_i$都可以取$0$到$10$之间的若干个数（不同未知数的可能的取值范围可能不同）。现在问，对于$[0,10n]$之间的任意数$t$，有多少种不同的未知数选择方案，可以使得所有未知数之和正好为$t$。

这个问题是一个很明显的用生成函数来求解的问题。对于第$i$个未知数$x_i$，我们建立一个多项式$f_i$，如果$x_i$可以取值$k$，那么我们就讲$f_i$的$x^k$项系数设置为1，否则设置为0。

可以发现$\prod_{i=1}^nf_i(x)$的$x^s$项系数表示的是有多少种不同方案，可以使得所有未知数之和为$s$。

错位排序的一些问题

问题1：给定一个$1$到$n$的排列$P$，要求计算有多少排列$S$满足对于所有$1\leq i\leq n$有$P_i\neq S_i$。其中$1\leq n \leq 10^6$

可以直接容斥解决。定义$A_i$表示满足$P_i=S_i$的所有排列$S$组成的集合。我们要求的是：$|\overline{S_1}\cap \ldots \cap \overline{S_n}|$。

注意到$S_i\cap S_j$表示的是所有已知$S_i=P_i,S_j=P_j$的排列，其大小应该为$(n-2)!$。

直接代入公式可以得出：$\sum_{i=0}^n {n\choose i}(-1)^i(n-i)!$，这就是要求的结果，提前预处理组合数，可以在$O(n)$时间复杂度内计算出结果。

问题2：给定一个$1$到$n$的排列$P$，其中$P$的$k$个位置为空（表示这些位置不限制）。设$g(n,k)$表示有有多少排列$S$满足对于所有$1\leq i\leq n$有$P_i\neq S_i$，要求输出$g(0,0),g(1,0),g(1,1),\ldots,g(n,0),g(n,1),\ldots, g(n,n)$。其中$1\leq n \leq 3000$

这个问题可以动态规划解决。定义$f(i,j)$表示还需要放置$i$个错排，之前还有$j$个元素未放入（对应还有$j$个空槽）。那么考虑转移公式有哪些贡献。

考虑处理第$i$个位置，以及其禁止放置的元素$P_i$，那么有四种情况：

1. $P_i$不会放入之前$j$个空槽中的任意一个，且之前的$j$个元素也不会放入第$i$个位置。
2. $P_i$会放入之前$j$个空槽中的任意一个，但是之前的$j$个元素也不会放入第$i$个位置。
3. $P_i$不会放入之前$j$个空槽中的任意一个，但是之前的$j$个元素中的一个会放入第$i$个位置。
4. $P_i$会放入之前$j$个空槽中的任意一个，且之前的$j$个元素中的一个会放入第$i$个位置。

于是可以推出转移公式为$f(i,j)=f(i-1,j+1)+2j\cdot f(i-1,j)+j^2\cdot f(i-1,j-1)$

接下来我们考虑怎么计算$g(i,j)$，容易发现当$j=0$时，直接有$g(i,0)=f(i,0)$。接下来我们考虑其它情形。我们可以这样思考，现在我们有$j$个位置没有约束，$i-j$个位置是存在约束的。我们可以将所有没有约束的位置按照位置的下标从小到大进行处理，因此如果$j>0$，那么我们可以选择最小下标的没有约束的位置，设置它的值，值可能是没有出现在$P$中的（对应的就是$j$种），也可能是出现在$P$中的（有$i-j$）种，后者会将一个有约束的位置转换为没有约束的。因此转移为$g(i,j)=j\cdot g(i,j-1) + (i-j)g(i-1,j)$，特殊的有$g(i,0)=f(i,0)$。

到此我们可以以$O(n^2)$的时间复杂度实现算法。

递增序列方案数

题目1：现在有$n$个位置数$a_1,a_2,\ldots, a_n$，要求为这$n$个位置数赋值，并且满足$L\leq a_i \leq R$，且序列严格递增，问有多少种不同的赋值方案（两个方案不同当且仅当存在一个未知数被赋予不同的值），其中$n\leq 10^5, 0\leq L\leq R\leq 10^9$

这个问题不难解决，由于是严格递增，因此我们每次从$m=R-L+1$个数中选择$n$个数后，这种选择方案正好对应一种有效的赋值方案。因此总的赋值方案为${m \choose n}$。

题目2：现在有$n$个数$a_1,a_2,\ldots, a_n$，要求为这$n$个数赋值，并且满足$L\leq a_i \leq R$，且序列非严格递增，问有多少种不同的赋值方案（两个方案不同当且仅当存在一个未知数被赋予不同的值），其中$n\leq 10^5, 0\leq L\leq R\leq 10^9$

题目2不能用题目1的方式解决，因为存在重复计算。我们引入新的一些变量$d_1,d_2,\ldots,d_n$，其中$d_i=a_i-a_{i-1}$，特殊的$d_1=a_1-L$。$a_i$序列上的非严格递增就变成了$d_i$序列非负，而$a_i$序列的左右边界就变成了$L+d_1+d_2+\ldots+d_n\leq R$。我们可以引入一个新的非负未知变量$x$，将不等式转换为等式$d_1+d_2+\ldots+d_n+x=R-L$。每个$d_i$序列的赋值方案与$a_i$序列的赋值方案正好一一对应，其方案数可以通过隔板法计算得到：${R-L+n\choose n}$。

其实这道题还有一种思路，就是记录$c_i$表示$i$这个数在结果的序列中出现的次数，那么很显然有$c_i\geq 0$且$\sum_{i=L}^Rc_i =n$，即给出$R-L+1$个非负未知数，求多少种方案能使得它们的和恰好为$n$，结果自然是${n+R-L\choose n}$。

题目3：现在有$n$个位置数$a_1,a_2,\ldots, a_n$，要求为这$n$个位置数赋值，并且满足$L_i\leq a_i \leq R_i$，且序列严格递增，问有多少种不同的赋值方案（两个方案不同当且仅当存在一个未知数被赋予不同的值），其中$n\leq 200, 0\leq L_i\leq R_i\leq 10^9$

我们可以将所有边界排序，之后利用这些边界将取值范围分隔为$O(n)$个区间。之后我们可以在上面进行DP，记录$dp(i,j)$表示仅考虑前$j$个数，且这$j$个数仅从前$i$个区间中取值，有多少种方案。可以很容易得出转移关系：$dp(i,j)=\sum_{k=0}^jdp(i-1,k)f(i,j-k)[k+1到第i个数的取值范围都包含第i个区间]$，这里$f(i,j-k)$表示从第$i$个区间中取出长度为$j-k$的严格递增序列的方案数，这个题目1已经解答了。总的时间复杂度为$O(n^3)$。

题目4：现在有$n$个位置数$a_1,a_2,\ldots, a_n$，要求为这$n$个位置数赋值，并且满足$L_i\leq a_i \leq R_i$，且序列非严格递增，问有多少种不同的赋值方案（两个方案不同当且仅当存在一个未知数被赋予不同的值），其中$n\leq 200, 0\leq L_i\leq R_i\leq 10^9$

同题目3，但是$f(i,j-k)$表示从第$i$个区间中取出长度为$j-k$的非严格递增序列的方案数，这个已经由题目2解答过了。

题目5：给出一颗$n$个顶点树，树根为1。问这颗树有多少拓扑排序的方案，将结果模上$p=10^9+7$。（如果树中存在边$(u,v)$，且$u$是$v$的父亲，那么$u$必须排在$v$之后）数据满足$n\leq 10^6$

考虑以某个顶点$u$为根的排序数为$f(u)$，那么很显然要对其排序等价于对所有子树进行排序，之后将子树合并。比如说$u$下有孩子$a$、$b$、$c$，那么$f(u)=f(a)f(b)f(c)\frac{(S_u-1)!}{S_a!S_b!S_c!}$，其中$S_u$表示以$u$为根的子树拥有多少孩子。

这样我们只需要遍历一次树就可以算出结果了，加上预处理组合所需要的时间，总的时间复杂度为$O(n)$。

题目6：给出一颗$n$个顶点树，树根为1。现在要求给每个顶点赋值为$1$到$m$中某个数，要求每个顶点分配到的数不同，且要求每个顶点的数都必须小于自己的父亲。问有多少种方案，结果对$p=10^9+7$取模。（两种方案不同当且仅当存在一个顶点，在两个方案中被赋予相同的值）数据满足$n\leq 10^6，m\leq 10^9$

首先利用题目5的方式计算出所有的拓扑排序的方案数$T$，接下来对于一个拓扑排序得到的序列，我们要为其以递增的方式分配$1$到$m$中的数，每个数最多出现一次。那么结果就是$T{m \choose n}$，由于$m$比较大，我们这边利用${m\choose n}=\frac{m\cdot \ldots (m-n+1)}{n!}$公式求解即可，总的时间复杂度为$O(n)$。

题目7：给出一颗$n$个顶点树，树根为1。现在要求给每个顶点赋值为$1$到$m$中某个数，且要求每个数都必须小于等于自己的父亲。问有多少种方案，结果对$p=10^9+7$取模。（两种方案不同当且仅当存在一个顶点，在两个方案中被赋予相同的值），数据满足$n\leq 5000, m\leq 10^9$

我们记录函数$f_u(i)$表示以顶点$u$为根的子树，如果$u$被赋值为$i$，整颗子树的方案数。那么当$u$是叶子顶点的时候，一定有$f_u(x)=1$。同时我们顺便定义$F_u(x)=\sum_{i=1}^xf_u(i)$，即前缀和函数。

现在考虑任意一个顶点$u$，假如其有三个子顶点$a,b,c$，那么一定有$f_u(i)=F_a(i)F_b(i)F_c(i)$。

由于$1$是多项式，而任意多项式的前缀和还是多项式，多项式的乘积依旧是多项式，因此对于任意顶点$u$，$f_u(x)$和$F_u(x)$都是多项式。

注意到当一个多项式从某个顶点沿着向父亲的边来到父亲时，需要修正为前缀和函数，这时候多项式的阶数会增加1。总共有$n-1$条边，而叶子顶点都是$0$阶多项式，因此我们可以断定$f_1(x)$是$n-1$阶多项式，而$F_1(x)$是$n$阶多项式。

我们想要的结果实际上是$F_1(m)$。

注意到$f_u(x)$要修正为$F_u(x)$，我们必须要借助多项式插值技术，但是这里每次插值的时间复杂度是$O(n^2)$，总共最多会发生$O(n)$次插值，因此最坏情况下时间复杂度会提高到$O(n^3)$。因此我们需要使用一个技巧，我们并不以系数的形式保存多项式，而是以点值的形式保存多项式。我们需要计算出每个多项式在$1,\ldots,n+1$共$n+1$个点上的值，这与我们就有能力以$O(n)$的时间复杂度将多项式修正为前缀和形式，以及$O(n)$的时间复杂度内完成多项式乘法。（注意这里提到的所有多项式在1处的值都应该是1）。

总的时间和空间复杂度是$O(n^2)$。

提供一道CF题目。

题目8：给出一颗$n$个顶点树，树根为1。现在要求给每个顶点赋值为$1$到$m$中某个数，且要求每个数都必须小于自己的父亲。问有多少种方案，结果对$p=10^9+7$取模。（两种方案不同当且仅当存在一个顶点，在两个方案中被赋予相同的值），数据满足$n\leq 3000, m\leq 10^9$

题目7的严格递减版本。现在考虑任意一个顶点$u$，假如其有三个子顶点$a,b,c$，那么一定有$f_u(i+1)=F_a(i)F_b(i)F_c(i)$。

我们为每个多项式维护$2n$个点的值，分别为$1,2,\ldots, 2n$。这里我们定义$D_u$表示$u$的高度，一个顶点的高度为其到子树内最远的叶子顶点的距离。而对于顶点$u$，其真正具有意义的点值是$D_u+1,D_u+2,\ldots, 2n+1$。

最终的做法也是插值出多项式求解。

问题9：给出一个$1,2,\ldots,n$的排列，判断是否可以将排列拆分为两个递增序列（空序列也认为是递增序列），如果可以，输出任意一种拆分方案，其中$n\leq 10^6$

我们维护两个递增序列，且由于递增序列只有最后一个元素会对后面的结果产生影响，因此我们可以始终假设第一个递增序列的尾部元素恒小于第二个递增序列的尾部元素。

这里我们可以使用一个贪心策略。当新加入一个元素的时候，若它比第二个递增序列尾部的元素还要大，就放在第二个序列尾部，否则放在第一个序列尾部（如果放不下就无解）。

由于前$i$个元素中的最大值一定会作为第二个递增序列尾部出现，因此我们要尽可能保证第一个序列尾部的元素尽可能小。

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

问题10：要求计算$1,2,\ldots,n$的所有排列中，有多少排列可以拆分为两个递增序列（空序列也认为是递增序列），结果模上某个素数$p$，其中$n\leq 1000$

我们可以利用动态规划解决这个问题。定义$dp(i,j)$表示两个递增序列的总长度为$i$的时候，已经使用的数中最大值为$j$有多少种递增序列。

那么可以推出转移公式：

$$dp(i,j)=\sum_{k=1}^j dp(i-1,k)$$

利用前缀和技术可以$O(n^2)$求解。

问题11：将$1,2,\ldots,n$这些数字加入按顺序加入到一个双端队列中（可以加入到任意一端），之后以任意顺序从双端队列弹出元素形成一个排列。问形成的排列中有多少排列，第$k$个元素为$1$。结果对某个素数取模。($k\leq n\leq 1000$)

首先需要发现所谓的加入双端队列，实际上是维护了两个栈，栈中的元素从栈底到栈顶递增。

之后从两个栈总共弹出$k-1$个元素后，一个栈为空，之后弹出$1$，最后对于剩下的一个非空栈，其中元素有$n-k$个，对应的形成的序列为$2^{n-k-1}$（如果两个栈都空就只有1种序列）。

由于前$k-1$个元素是由两个递减序列所形成的，现在的问题就是求解长度为$k-1$的可以拆分为两个递减序列的序列有多少种，之后乘上$2^{n-k-1}$即可。求解的方式在问题10中已经提到过了。

提供一道Atcoder题目。

生成函数

生成函数可以用于求解大量统计方案数问题。其方式就是定义一个多项式$P(x)=\sum_{i}c_ix^i$，其中系数就$c_i$表示做$i$次决策的方案数。现在考虑两个不同方案的生成函数$A$和$B$，我们现在希望求两个方案总共决策$k$次的方案数，其实就是求$A(x)B(x)$的$x^k$项的系数。

题目1：给定大小为$n$的集合$A={a_1,\ldots,a_n}$，对于任意$A$的子集$S$，记$f(S)=\prod_{a\in S}a$，同时记$g(i)=\sum_{S\subseteq A\land |S|=i}f(S)$。现在要求输出$g(1),\ldots,g(n)$。其中$n\leq 10^5$。

一般这种问题需要用DP求解，通过各种优化时间复杂度可以达到$O(n^2)$，但是还是过不了的。

但是生成函数可以给出更优的做法。我们定义$n$个多项式$P_1,\ldots, P_n$，其中$P_i(x)=1+a_ix$。会发现$\prod_{i=1}^nP_i$实际上就等于$g(i)$。而要计算$n$个一阶多项式的乘积，可以用分治+FFT的技术实现。时间复杂度为$O(n(\log_2n)^2)$。

题目2：给定两个多重集合$A$和$B$，其中$1\leq |A|,|B|\leq 10^6$，且对于$A$与$B$中的任意元素$x$都有$0\leq x\leq 10^6$。现在定义$f(n)=\sum_{a\in A}\sum_{b\in B}[b-a\equiv n]$，要求输出所有的$f(0),f(1),\ldots,f(10^6)$。

这个问题可以用bitset来优化，时间复杂度为$O(\frac{10^{12}}{64})$。

这和个问题可以用生成函数解决。定义两个多项式$P$和$Q$，其中$P_i$表示$i$在$A$中的出现次数，同理$Q_i$表示$i$在$Q$中的出现次数。可以发现

$$f(n)=\sum_{i=n}P_iQ_{i-n}$$

上面的部分是$P$和$Q$等差卷积后$x^n$项的系数。因此我们只需要将$P$和$Q$等差卷积后得出所有项的系数。时间复杂度为$O(10^6\log_210^6)$。

题目3：给定一个序列$a_1,a_2,\ldots,a_n$，要求计算有多少$i<j<k$，满足$a_i\cdot a_j\cdot a_t=T$，其中$T$是给定常量，且$1\leq a_i\leq 10^6$, $1\leq n\leq 10^6$，$1\leq T\leq 10^6$。

首先顺序处理起来比较麻烦，但是我们可以求出无序情况下的结果数$ans$，那么答案就是$\frac{ans}{3!}$。

这个问题中要求下标不同，这个条件处理起来太麻烦了，我们用容斥忽略这个条件，具体来说就是记$A$表示所有满足总和等于$T$的三元组中满足$i\neq j$的三元组，$B$表示满足$j\neq k$的三元组，$C$表示满足$k\neq i$的三元组。那我们要求的是$|A\cap B\cap C|$的大小。

对于全集，我们可以用生成函数来求。具体做法就是定义一个生成函数$P$，其中$P_i$表示$i$在序列$a$中的出现次数。那么答案就是$P^3(x)$的$x^T$项的系数。

对于$|\overline{A}|$的统计，即我们已知$i$和$k$是相同的，我们可以遍历可能的$n$种$i$和$j$的共同下标，定义一个新的多项式$Q$，$Q_i$表示有多少下标$j$满足$a_j^2=i$。那么答案就是$P(x)Q(x)$的$x^T$项系数。对于$|\overline{B}|$和$|\overline{C}|$，其值与$|\overline{A}|$相同。

对于其余情况，一定有三个下标都相同，我们可以暴力枚举所有$n$种下标，来统计。

因此最终总的时间复杂度为$O(n+10^6\log_210^6)$。

网格问题

题目1：给定一个$n\times m$的矩阵，要求每个网格都要放一个非负数，且第$i$行所有网格值的和为$a_i$，且要求每一列的网格和为正数。满足该条件的放置数记作$f(m)$，要求分别输出$f(1),\ldots,f(M)$。其中$n\leq 10, m\leq 10^5, a_i\geq 1$。

记$x_{i,j}$表示网格$(i,j)$所放的数字。记$g(m)$表示列数为$m$，且忽略每列的和都必须为正数这个条件下的放置数。可以发现$g(m)=\prod_{i=1}^n{m+a_i-1 \choose m}$。我们可以通过容斥从$g$中搞出$f$。

$$\begin{aligned} f(m)&=\sum_{i=0}^m(-1)^i{m \choose i}g(m-i)\\ &=m!\sum_{i=0}^m[(-1)^i\frac{1}{i!}][g(m-i)\frac{1}{(m-i)!}] \end{aligned}$$

可以发现$\sum$符号内部的内容可以通过对两个多项式计算卷积得到。因此我们可以$O(M\log_2M)$时间复杂度内求出结果。

提供一道CF题目

题目2：给定一个$n\times m$的矩阵，每个单元中都有一个数，其中单元$(i,j)$的数为$a(i,j)$，且第一列和第一行的数均为$1$。且对于$1<i,j$，满足$a(i,j)=a(i-1,j)+a(i,j-1)$，要求计算$a(n,m)$，其中$n,m\leq 10^5$

这个问题实际上要求的是从第$(0,j)$以及$(i,0)$到$(n,m)$的路径总数，答案为$\sum_{i=1}^n{n+m-1-i\choose m-1}+\sum_{i=2}^m{n+m-1-i\choose n-1}$。我们可以$O(n+m)$求解。

统计多重集合

给定包含$n$种元素的多重集合，第$i$种元素出现$c_i$次。

有多少种排列？就是普通的多重排列。

$$\frac{(\sum_{i=1}^nc_i)!}{\prod_{i=1}^nc_i!}$$

有多少不同的子集？

$$\prod_{i=1}^n(c_i+1)$$

题目1：给定一个大小为$n$的背包。记$c_i$为重量为$i$的物品种类的数量。要求找出能将背包装满的物品的多重集合的数目，结果模上$10^9+7$。其中$1\leq n\leq 1000$，$1\leq c_i\leq 10^9$

很显然这是一个背包问题，但是物品的种类数过多，所以不能用常规的动态规划求。

我们可以记$dp(i,j)$表示用重量不超过$i$的物品，有多少不同的多重集合可以填充大小为$j$的背包。

于是乎可以得到转移：

$$dp(i,j)=\sum_{k=0}^{\lfloor \frac{j}{i} \rfloor}dp(i-1,j-ki){c_i+k-1 \choose k-1}$$

由于${c_i+k-1 \choose k-1}$中$k-1$非常小，我们可以$O(k)$求解，但是特殊的可以发现$k$是递增的且${c_i+k-1 \choose k-1}={c_i+k-2 \choose k-2}\frac{c_i+k-1}{k-1}$，因此我们可以$O(1)$递推求出每个组合数。

因此上面的递推公式可以$O(\frac{j}{i})$求出，要求所有的状态总的时间复杂度为$O(\sum_{i}^n\sum_{j}^n\frac{j}{i})=O(n^2\log n)$。

提供一道问题。

Hockey Stick Identity

$$\sum_{i=0}^n {i\choose r}={n+1\choose r+1}$$

可以归纳证明，当$n\leq r$的时候显然成立。考虑$n>r$的情况下，有

$$\sum_{i=0}^n {i\choose r}={n\choose r+1}+{n\choose r}={n+1\choose r+1}$$

提供一些题目。

参考资料

• 斯特林数WIKI
• https://www.cnblogs.com/hchhch233/p/10016543.html
• https://blog.csdn.net/zhouyuheng2003/article/details/85055709
• https://en.wikipedia.org/wiki/Hockey-stick_identity