组合数学

Published: by Creative Commons Licence

  • Tags:

Catalan数

理论

假设我们有n个1和m个-1,我们希望排列这n+m个数,并且要求排列$a_i$满足下面条件:

  • 对于任意$0 \leq j \leq n+m$,都有$\sum_{i\leq j} a_i \geq -k$。

我们希望求出有多少种不同的排列满足条件。

首先如果$m > n+k$,那么有效排列数一定为0。下面仅考虑$m\leq n+k$的情况。

我们知道总共的排列数为$n+m \choose n$,因此只要减去不满足条件的排列数,就可以得到满足的排列数了。下面我们考虑怎么计算不满足条件的排列数。

对于某个不满足条件的排列$B$,一定能找到最小的下标,一定能找到最小的下标j,使得,使得$\sum_{i\leq j} a_i = -(k+1)$。我们将排列。我们将排列B的从第的从第$j+1$个下标开始的值全部取相反值,即改为,改为。这样我们就得到了一个个下标开始的值全部取相反值,即$1$改为$-1$,$-1$改为$1$。这样我们就得到了一个$m-1-k$个和个$1$和$n+1+k$个的排列。要还原,我们只需要找到最小的下标个-1的排列。要还原,我们只需要找到最小的下标j,使得,使得$\sum_{i\leq j} a_i = -(k+1)$,将后面的元素取反就好了。这似乎暗示了,将后面的元素取反就好了。这似乎暗示了n个和个1和m个的无效排列与个$-1$的无效排列与$m-1-k$个和个$1$和$n+1+k$个的排列之间存在类似双射的关系。首先很明显从前者到后者一定是单射,即不同的输入对应不同的输出,同时由于个$-1$的排列之间存在类似双射的关系。首先很明显从前者到后者一定是单射,即不同的输入对应不同的输出,同时由于$m-1-k$个和个$1$和$n+1+k$个的排列中必定能找到这样的个$-1$的排列中必定能找到这样的$j$,使得前$j$个数的和为$-(k+1)$,因此映射是满射。

满射意味着$n$个$1$和$m$个$-1$的无效排列与$m-1-k$个1和$n+1+k$个-1的排列数目相同,即总有效排列数为:

问题1:用$n$个左括号和$n$个右括号能组成多少有效的括号序列。

首先一个括号序列有效,当且仅当排列中所有前缀部分中,左括号数不少于右括号数。如果我们将左括号视作1,右括号视为-1,取$k=0$,那么就转换为Catalan数问题了。有效数为

问题2:给定一个$n\dot n$的网格,我们从$(0,0)$出发。假如我们现在位于$(i,j)$,且$i<n$,那么我们下一步可以到达$(i+1,j-1),(i+1,j),(i+1,j+1)$。问最后停止在$(n,k)$的总方案数有多少,这里$l\leq k\leq r$。其中$n\leq 10^5$,结果模上某个素数$p$

这个问题利用了catalan数的一个特性,设$m$为向上走的次数和向下走的次数的总和,记$x$表示向上走的次数,那么$x$一定符合:$l\leq x-(m-x)\leq r$,即$\lceil\frac{m+l}{2}\rceil\leq x\leq \lfloor\frac{m+r}{2}\rfloor$。可以发现:

而我们只需要枚举$m$即可得到所有的可能:

上面的公式可以$O(n)$计算。

提供一道CF类似的题目(但是是毒瘤题,需要使用扩展卢卡斯定理求组合数)。

隔板法

对于n个非负变量$x_1,x_2,\ldots,x_n$,问满足下面等式的分配方案有多少种:

这等价于m个小球,我们向其中插入$n-1$个挡板,将其切分为n部分的方案数,因此我们可以直接得出方案数为:

现在考虑满足下面不等式的分配方案有多少种:

我们现在进行推导:

现在考虑一个更简单的不等式的分配方案:

进行推导:

其实这个问题也等价于下面等式成立的前提下,前n个变量有多少种分配方案。

由于前n个变量唯一决定变量$x_{n+1}$,因此等于等式的总分配数。

题目1:考虑所有非负整数变量$x_1,\ldots,x_n$的赋值方案,要求满足$x_1+\ldots+x_n=m$。考虑某个赋值方案,记任意一个下标集合$A$,定义这个下标集合的权重为$w(A)=\prod_{i\in A}x_i$。现在要求求对于所有大小为$k$的下标集合,计算所有方案下它们权重的总和。

由于这些变量仅仅指标不同,因此对于两个大小均为$k$的下标集合,它们在所有方案下权重之和应该是相同的。于是乎我们要考虑在所有方案下,$\prod_{1\leq i\leq k}x_i$的值的和,最后乘上${n\choose k}$就是我们要求的结果了。

现在考虑怎么计算$\prod_{1\leq i\leq k}x_i$,DP当然可以,但是时间复杂度为$O(n^2)$。也可以用生成函数,但是有点复杂,而且时间复杂度也好不到哪里去。

这个问题实际上有$O(1)$的做法(不考虑预处理$O(n)$时间)。非常简单,这个问题等价于将一个长度为$m$个线段分解为$n$个长度为整数的线段,且前$k$个线段需要从中间某个整数位置(不能和左边界重合)再选择一个中间点,问最终有多少不同的方案(长度为$L$的线段,选择中间点有$L$种可能)。而这个问题等价于直接将原序列拆分成$n+k$段,其中特定的$k$段不能为空。这个可以通过隔板法解决,即${n+m-1 \choose n+k-1}$。

题目2:考虑这样一个问题,有$n$个非负偶数$x_1,\ldots,x_n$和$m$个非负奇数$y_1,\ldots,y_m$,要求计算有多少种不同的赋值方案,满足$x_1+\ldots+x_n+y_1+\ldots+y_m\leq K$。将结果模上某个素数$p$。其中$0\leq n,m\leq 100$,$K\leq 10^{18}$。

我们额外加入一个非负变量$z$,因此问题要我们计算有多少不同的赋值方案,满足$x_1+\ldots+x_n+y_1+\ldots+y_m+z=K$。

一般的思路是用生成函数来求解,但是不好求解。

我们可以发现$n,m$非常小,因此我们可以考虑用动态规划来求解。记$dp(i,j)$表示前$j$个未知数总和为$i$的方案赋值数,那么我们可以用动态规划来求解,时间复杂度为$O((n+m)K)$。

但是仔细观察可以发现动态规划的递推公式是线性关系。即有$A\cdot dp(i,?)=dp(i+1,?)$,其中$A$是一个$R\times R$的矩阵,其中$R=401$。

于是问题的时间复杂度为$O(R^3\log_2K)$,过有些勉强。

这里可以考虑用BM算法来优化。我们可以用$O(R^2)$的时间复杂度搞出前面$2R$项,之后用BM算法推出最短递推公式。之后用多项式快速模$O(R^2\log_2K)$求解。

提供一道题目:https://atcoder.jp/contests/aising2020/tasks/aising2020_f

容斥原理

假设有全集$S$,以及全集的若干子集$A_1,A_2,\ldots, A_k$。

在实际应用中要统计多个子集的交集的大小是比较容易的,但是要统计多个子集的并集的大小则比较困难。对于这种情况,我们可以使用容斥原理将并运算简化为若干次交运算。

容斥原理的公式如下:

例子1

统计1~100中能被2,3同时整除的数的数目。

记$S={1,2,\ldots, 100}$,记$A_i$表示$S$中所有能被i整除的数的集合。那么我们要求的实际上就是:

最值反演(min-max容斥)

证明:

考虑第一个公式。假设x为S中的第i+1大元素。那么x的展开项系数为:

因此只有当i为0时,系数为1,其它情况都为0。第二个公式同理可证。

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

类型1

对于所有 ,要求计算:

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

其中 可以表示为下面两个函数的卷积

利用快速卷积可以在$O(n\log_2n)$的时间复杂度内实现。记 ,那么

类型2

对于所有 ,要求计算:

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

其中右边部分 是等差卷积,即令

那么有

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

类型3

统计:

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

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

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

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

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

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

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

Burnside定理

Burnside定理用于计算集合X的非等价着色数。

设$C$是$X$的着色集合,$G$是$X$的置换群,且$G$作用在$C$上,即$\forall f \in G,c\in C(f \ast c \in C)$。

定义函数$C(f)$:

记$N(G,C)$表示在$G$作用下,$C$中非等价的着色数目。

Burnside公式如下:

例子1

举个简单的例子,将n个不同的对象放在一个环上,有多少种不同的放法。

如果一种方法可以通过另外一种方法通过旋转得到,就认为两种方法等价,比如n=3的情况下,(1,2,3)与(2,3,1),(3,1,2)被认为是等价的方法。

容易发现$G={r^0,r^1,\ldots, r^{n-1}}$,其中$r=(2,3,\ldots, n, 1)$。

由于每个对象都不同,因此一定有$C(r^1)=C(r^2)=\ldots = C(r^{n-1})=\emptyset$。而$C(r^0)$,由于所有着色方案在$r^0$下保持不变,因此$C(r^0)=C$。

带入到Burnside公式中,可以得到:

是不是很简单啊…

Polya定理

一个置换可以分解为若干个循环节,比如$(2,1,3)$,它可以被分解为两个循环节$[12][3]$。一个置换分解的循环节个数是固定的。

记$#(f)$表示置换f分解后的循环节数目。

对于置换$f$,其分解的循环节,长度为$i$的有$e_i$个循环节,定义$type(f)=(e_1,e_2,\ldots, e_n)$。

由于$f$分解的循环节的总长度一定是$n$,因此满足

引入$n$个变量$z_1,z_2,\ldots, z_n$,记$mon(f)=z_1^{e_1}z_2^{e_2}\ldots z_n^{e_n}$。

定义函数$P(G)$如下:

Polya定理给出了下面命题:

假设有$k$种不同的颜色,有$N(G,C)=P_G(k,k,\ldots, k)$。

假设有$k$种不同的颜色,限制第i种颜色必须正好出现$p_i$次,我们引入$k$个新的变量$u_1,u_2,\ldots, u_k$代表$k$种颜色,我们可以保证$N(G,C)$的生成函数

即$N(G,C)$是上式展开后项$u_1^{p_1}u_2^{p_2}\ldots u_k^{p_k}$的系数。

例子1

对于一个四边形,每个顶点都可以用k种颜色着色。问有多少种不等价的着色方案。

如果一个着色可以通过另外一种着色方案,通过旋转,则认为两个着色不等价。

首先G由下面元素组成:

利用Polya定理计算:

设$k=2$带入可以得到$P_G(2,2,2,2)=6$。

非连续0问题

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

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

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

  • 10
  • 1

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

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

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

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

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

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

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

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

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

统计选球方案

问题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$次的所有方案的集合。那么结果为:

问题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$的方案组成的集合。那么问题的解就是:

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

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

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

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

问题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}$。

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

容斥与动态规划

容斥与动态规划可以很好地结合,因为容斥真正重要的只有奇偶性,这意味着我们用动态规划来表示容斥的各种选择情况。

比如这道问题,提供一颗树,将树上2n个顶点分为n类,每类两个顶点,要求对于任意一条边,存在一类顶点在边删除后属于不同的连通块。这个问题我们可以通过对边进行容斥来解决,在树上进行DP,定义$dp(u,i,k)$表示以u为根的子树正好i个顶点未分组,且不能被覆盖的边的数目模2的结果为k。这样我们就可以发现可以用DP来统计最终的结果。

还有一个类似的问题,需要利用到容斥的奇偶性结合DP解决的问题

统计所有和方案数问题

考虑有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$。

拆分数方案

给定方程$\sum_{i=1}^ni\cdot x_i=m$,其中$x_i\geq 0$,$m\leq n$,问这个公式有多少种不同的赋值方案,记其为$h(m)$。

很容易想到一个暴力DP,记录$f(i,j)$表示仅考虑$1$到$i$,有多少方案可以使它们的和为$j$。可以得出$f(i,j)=f(i-1,j)+f(i,j-i)$。但是这种做法是$O(n^2)$的。

我们可以考虑分块,块的大小为$k$,我们记录$A(x)$表示用$1,2,\ldots, k-1$这些数组成$x$的方案数,而记录$B(x)$为用$k,\ldots, n$这些数组成$x$的方案数。

那么有$h(i)=\sum_{0\leq j\leq i}A(j)B(i-j)$。我们可以利用卷积得到$h(0),h(1),h(2),\ldots, h(n)$。

函数$A$,我们可以直接用暴力DP的方式进行计算。

对于函数$B$,我们记录$g(i,j)$表示$\sum_{t=k}^n x_t = i$的前提下使得$\sum_{t=k}^n t\cdot x_t=j$的方案数。可以分两种情况讨论,如果方案中下标最小的非0未知数的下标为$k$,那么此时方案数为$g(i-1,j-k)$,否则此时有$\sum_{t=k+1}^n t\cdot x_t=j\Rightarrow i+\sum_{t=k}^{n-1} t\cdot x_{t+1}=j$,即此时的方案数为$g(i,j-i)$。利用这两种情况,可以得出递推公式:$g(i,j)=g(i-1,j-k)+g(i,j-i)$。注意到$g$只有$(n-k+1)\cdot \frac{n}{k}=O(\frac{n^2}{k})$个有效状态。

整体的时间复杂度为$O(nk+\frac{n^2}{k}+n\log_2n)$,如果我们取$k=\sqrt{n}$,那么时间复杂度则为$O(n\sqrt{n}+n\log_2n)$。

五边形数定理

公式:

问题1:要求计算$\sum_{i=1}^ni\cdot c_i=n$中,$0\leq c_1,\ldots,c_n$,有多少种$c_1,\ldots,c_n$的赋值方案

可以用生成函数求解,我们要求的是$f(x)$的$x^n$项的系数:

可以发现:

这里我们可以利用五边形定理快速求出$\frac{1}{f(x)}\mod x^{n+1}$,之后求逆即可。

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

问题2:要求计算$\sum_{i=1}^ni\cdot c_i=k$中,$0\leq c_i\leq a_i$,有多少种$c_1,\ldots,c_n$的赋值方案分别满足$k=1,2,\ldots,n$。输入满足$0\leq a_1<a_2<\ldots<a_n$,其中$n\leq 10^5$。

可以用生成函数求解,我们要求的是$f(x)$:

由于$0\leq a_1<\ldots <a_i$,因此有$a_i+1\geq i$,故$(a_i+1)\cdot i\geq i^2$。因此$(1-x^{(a_i+1)\cdot i})$中最多$\sqrt{n}$项不为$1$。因此分子部分的乘积和,我们可以$O(n\sqrt{n})$计算出来。

分母部分就是一个典型的五边形定理的应用了。求出来后分子乘上分母的逆多项式即可得到结果。

提供一道题目

错位排序的一些问题

问题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$个球,第$i$个球上标着数字$i$,同时有颜色$c_i$。要求统计有多少不同的排列,满足排列中任意两个相邻的球的颜色不同,将结果模素数$p$后输出。其中$\leq n\leq 500$,且$1\leq c_i\leq n$

我们可以用容斥来求。会发现容斥的情况实在是太多了,但是这是因为你是自上向下看(即利用公式求结果),如果你自下向上看(即先统计各种可能性,之后搭配容斥),就会发现这是可以实现的。

容斥的本质是我们要将一些球强行绑定起来,且它们的贡献的正负是由多少对球被绑定的奇偶性所决定的。

假设我们手头有$m$个球,将其分成$k$个绑块的方案数可以用隔板法计算,为$f(m,k)={m+k-1-k \choose k-1}\frac{m!}{k!}$。

接着我们定义$dp(i,j)$表示颜色前$i$种颜色的球堆中,共被分成了$j$个绑定好的球的方案数。这里记$m$表示颜色为$i$的球的数目,容易得到转移方程:

接下来我们用这些计算结果来进行容斥,答案应该是

即如果我们发现最后分成$i$个绑定块,其可以对应$i!$种排列,同时$(-1)^{n-i}$用于确定该贡献在容斥公式种的正负。

总的时间复杂度为$O(n^3)$。

提供一道题目

题目2:有$n$个球,第$i$个球的颜色为$c_i$。要求统计有多少不同的排列,满足排列中任意两个相邻的球的颜色不同,将结果模素数$p$后输出。其中$\leq n\leq 500$,且$1\leq c_i\leq n$

这个问题和问题1的区别仅在于没有数字而已,我们可以先求出问题$1$,之后再除去数字带来的额外排列即可。时间复杂度相同为$O(n^3)$。

递归求排列组合的时间复杂度分析

排列时间复杂度

大家应该遇到这样的问题,比如说生成1到n的所有排列(其中n很小)。我们会写成:

void gen(int[] perm, int i, boolean[] used) {
    if(i == -1){
        //排列已经生成,做些操作
        return;
    }
    for(int j = 0; j < used.length; j++){
        if(used[j]){
            continue;
        }
        used[j] = true;
        perm[i] = j;
        gen(perm, i - 1, used);
        used[j] = false; 
    }
}

那么这个递归操作的时间复杂度是多少呢?

我们可以这样分析,当gen的参数$i$为$k$的时候,gen会被调用$\frac{n!}{(k+1)!}$,因此总共调用的次数为$\sum_{i=0}^{n-1}\frac{n!}{(k+1)!}=\sum_{i=1}^{n}\frac{n!}{k!}=n!\sum_{i=1}^{n}\frac{1}{k!}$。

注意到$k\geq 4$的时候一定有$k!>2^k$,因此我们可以直接估计出

因此总的函数调用次数会被约束在$2n!$次以内。而由于每次调用的时间复杂度都是$O(n)$,因此总的时间复杂度为$O(2n\cdot n!+n!M)$,其中$M$是排列生成完毕后操作的时间复杂度。

这个算法在$n\leq 10$的情况下还是可以接受的(72576000),而在$n=11$的时候就非常危险了(878169600)。

组合时间复杂度

在计算容斥或者枚举大小为$n$的集合的子集的时候,我们会这样写:

void gen(int[] bits, int i, int sum){
    if(i == -1){
        //组合已经生成完毕,做一些操作
        return;
    }
    gen(bits, i - 1, sum);
    bits[i] = 1;
    gen(bits, i - 1, sum + 1);
    bits[i] = 0;
}

那么这个算法的时间复杂度是多少呢。容易发现gen在$i=k$的时候会被调用总共$2^{n-1-k}$次。因此总的调用次数为

而每次调用的时间复杂度都是常数,因此总的时间复杂度为$O(2^nM)$,这里$M$是每次组合生成完毕后的操作的时间复杂度。

组合生成函数的性能会比排列生成函数的快不少,主要原因是排列的增长速率过于吓人。一般组合生成函数在$28$以内都是比较安全的。

递增序列方案数

题目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$有多少种递增序列。

那么可以推出转移公式:

利用前缀和技术可以$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$中的出现次数。可以发现

上面的部分是$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$的棋盘,要求每行最少要放一个棋子,问有多少种不同的方法(两种方法不同当且仅当存在一个格子,一个方法放了棋子另外一个方法没放)。结果模素数。

直接上容斥:

时间复杂度为$O(\log_2n+\log_2m)$。

题目2:给定一个$n\times m$的棋盘,要求每行最少要放一个棋子且正好放$k$个棋子,问有多少种不同的方法(两种方法不同当且仅当存在一个格子,一个方法放了棋子另外一个方法没放)。结果模素数。

直接上容斥:

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

可以用生成函数优化。记$f(x)=\sum_{i=1}^m{m\choose i}x^i$,那么结果就是$f^n(x)$的$x^k$项的系数。时间复杂度为$O(k\log_2n \log_2k)$。

题目3:给定一个$n\times m$的棋盘,要求每列和每行至少要放一个棋子,问有多少种不同的方法(两种方法不同当且仅当存在一个格子,一个方法放了棋子另外一个方法没放)。结果模素数。

这道题可以通过容斥解决。

上面这个公式可以$O(n\log_2m)$求解。

提供一道题目

题目4:给定一个$n\times m$的棋盘,要求每列和每行至少要放一个棋子且正好总共放了$k$个棋子,问有多少种不同的方法(两种方法不同当且仅当存在一个格子,一个方法放了棋子另外一个方法没放)。结果模素数。

考虑容斥做法:

所以时间复杂度为$O(nm)$。

题目5:给定一个$n\times m$的矩阵,要求第$i$行放$a_i$个棋子,且每列都至少要放一个棋子。要求回答总共有多少不同的放置方法(两种方法不同,当且仅当最终形成的棋子的摆放不同),这里$n\leq 10, m\leq 10^5$

由于$n$非常小,我们可以用DP计算。记$dp(i,j)$表示考虑前$i$行,总共有$j$列上有棋子。可以推出转移公式:

直接计算的话时间复杂度为$O(m^2+nm)$。但是我们可以稍微转换公式:

可以发现加总公式中的内容可以通过多项式卷积进行计算。因此时间复杂度可以降低为$O(nm\log_2m)$。

网格问题

题目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$。

可以发现$\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$次。

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

有多少不同的子集?

题目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$的背包。

于是乎可以得到转移:

由于${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)$。

提供一道问题

参考资料