当前位置：首页 > news >正文

【6】组合计数学习笔记

news 来源：原创 2025/8/9 12:34:25

前言

~~关于今天发现自己连快速幂都忘记怎么写这件事~~

这篇博客是组合计数基础，由于大部分内容都是 $6$ 级，所以我就给整个提高级的组合数学评了 $6$ 级。

组合计数基础

加法原理与乘法原理

加法原理（分类计数原理）：完成一件事有 $n$ 类方法，第一类办法有 $m_i$ 种，第二类办法有 $m_2$ 种……第 $n$ 类办法有 $m_n$ 种，那么完成这件事的方法数（记为 $N$ ）为：

$N=m_1+m_2+\dots+m_n$

乘法原理（分步计数原理）：完成一件事有 $n$ 步，第一类步有 $m_i$ 种方法，第二步有 $m_2$ 种方法……第 $n$ 步有 $m_n$ 种方法，那么完成这件事的方法数（记为 $N$ ）为：

$N=m_1m_2\dots m_n$

加法原理步骤相互独立，任何一种都能独立完成这件事；乘法原理步骤缺一不可，缺少任意一种就不能完成这件事。

排列与组合

排列：从 $n$ 个不同元素中取出 $m$ 个元素，按照不同顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列，记作 $A^{m}_n$ 。

排列数计算公式：

$A^{m}_n=n(n-1)(n-2)\dots(n-m+1)=\frac{n!}{(n-m)!}$

组合：从 $n$ 个不同元素中取出 $m$ 个元素，并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合，记作 $C^{m}_n$ 。

组合数计算公式：

$C^{m}_n=\frac{A^{m}_n}{A^m_m}=\frac{n(n-1)(n-2)\dots(n-m+1)}{m!}=\frac{n!}{m!(n-m)!}$

与顺序有关的为排列问题，与顺序无关的为组合问题。

例题 $1$ ：

由 $0, 1, 2, 3, 4, 5$ 可以组成多少个没有重复数字的五位奇数?

由于首位和末位有特殊要求，应该优先安排，以免不合要求的元素占了这两个位置。

先排末位有 $C^1_3$ 种方法，再排首位有 $C^1_4$ 种方法，最后排剩下的有 $A^3_4$ 种方法。

最后由乘法原理得到答案 $N$ 为：

$N=C^1_3C^1_4A^3_4=288$

例题 $2$ ：

$7$ 种不同的花种在排成一列的花盆里,若两种葵花不种在中间也不种在两边,有多少不同的种法?

由于特殊的两种葵花有特殊要求，应该优先安排，以免不合要求的元素占了这四个位置。

先排两盆特殊的葵花有 $A^2_4$ 种方法，再排剩下的有 $A^5_5$ 种方法。

最后由乘法原理得到答案 $N$ 为：

$N=A^2_4A^5_5=1440$

组合数的性质：

$1$ ： $C^0_0=C^n_n=1$

$2$ ： $C^m_n=C^{n-m}_n$

原因：从 $n$ 个不同元素中取出 $m$ 个元素，也就是从 $n$ 个不同元素中不选择 $n - m$ 个元素，方法数一样。

$3$ ： $C^n_m=C^{n-1}_{m-1}+C^{n}_{m-1}$

原因：从 $n$ 个不同元素中取出 $m$ 个元素，如果其中一个元素不取，那么就变成了从 $n - 1$ 个不同元素中取出 $m$ 个元素；如果其中一个元素取，那么就变成了从 $n - 1$ 个不同元素中取出 $m - 1$ 个元素。再根据加法原理，得出这条性质。

组合数的求法

求法 $1$ ：杨辉三角递推（预处理）

适用范围： $n, m$ 较小。

根据组合数的第 $3$ 条性质，可以递推求出某一范围内的所有组合数。由于最后推完会发现其实是杨辉三角，所以也叫杨辉三角递推。

c[0][0]=1;
for(int i=1;i<=k;i++)c[i][0]=c[i][i]=1;
for(int i=1;i<=k;i++)for(int j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];

时间复杂度： $O (nm)$

求法 $2$ ：逆元（组合数取余）

适用范围：能保证逆元存在时。

由逆元的定义，我们可以推出这个式子：

$C^{m}_n=\frac{n!}{m!(n-m)!}=n!\times inv(m!)\times inv[(n-m)!]$

long long power(long long a,long long p,long long m)
{long long x=a,ans=1;while(p){if(p%2==1)ans=(x%m*ans%m)%m;p/=2;x=(x%m*x%m)%m;}return ans;
}long long get_c(long long n,long long k,long long m)
{k=min(k,n-k);long long r1=1,r2=1;for(int i=n-k+1;i<=n;i++)r1=(r1%m*i%m)%m;for(int i=1;i<=k;i++)r2=(r2%m*i%m)%m;return (r1%m*power(r2,m-2,m)%m)%m;
}

对于逆元，直接费马小定理或扩展欧几里得求就行了。【7】逆元学习笔记

时间复杂度： $O (n + m)$

二项式定理

二项式定理基本形式：

$(a+b)^n=\sum^{n}_{k=0}C^k_na^kb^{n-k}$

那么可以推出：

$(ax+by)^n=\sum^{n}_{k=0}C^k_n(ax)^k(by)^{n-k}=\sum^{n}_{k=0}(C^k_na^kb^{n-k})x^ky^{n-k}$

二项式定理可以通过数学归纳法证明，但因为个人实力有限 ~~（教练没讲）~~，就不证明了。

例题 $3$ ：

P1313 [NOIP2011 提高组] 计算系数

用杨辉三角递推求出组合数，直接套用二项式定理计算系数，用快速幂处理 $a^kb^{n-k}$ 即可。

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,a,b,c[1010][1010];
long long power(long long a,long long p,long long m)
{long long x=a,ans=1;while(p){if(p%2==1)ans=ans*x%m;p/=2;x=x*x%m;}return ans;
}int main()
{scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);c[0][0]=1;for(long long i=1;i<=k;i++)c[i][0]=c[i][i]=1;for(long long i=1;i<=k;i++)for(long long j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007;printf("%lld\n",((c[k][m]*power(a,n,10007))*power(b,m,10007))%10007); return 0;
}

例题 $4$ ：

CF1332E Height All the Same

考虑到可以在一个格子上码上两个方块，易得如果每个格子奇偶性相同，则一定可以到达同样高度。对于任意点对 $(x, y)$ ，我们可以通过找到一条路，路径上可以互达的两点有一边相邻， $x\to b\to c\dots\to y$ ，每次增加相邻两个点，这样除了 $x, y$ 各自加 $1$ ，其余的点均加 $2$ ，奇偶性不变。

所以，我们每次可以改变两个点的奇偶性。对于 $nm$ 为奇数的情况，我们一定可以找到一种奇偶性的数有偶数个，每次修改一对为另一种奇偶性。也就是说，对于任意一种初始情况，均可以修改至完全相同。数量为 $r-l+1)^{nm}$ 。

对于 $nm$ 为偶数的情况，只有奇偶数个数均为偶数时才满足要求。考虑枚举奇数数量方案数累加，运用乘法原理求出每种情况的方案数。我们先选位置，如果现在有 $i$ 个奇数，则有 $C_{nm}^{i}$ 种选法。设 $[l, r]$ 有 $a$ 个奇数， $b$ 个偶数，则奇数有 $a^i$ 种方法，偶数有 $b^{nm-i}$ 种选法。

$\sum_{i=0,2\mid i}^{nm}C_{nm}^{i}a^ib^{nm-i}$

看到这个式子，容易联想到二项式定理。但是这个式子不好转化，需要转化为对于每一个 $i$ 都有一个计算式。我们考虑用整体减去部分，可是还是不行。顺着这个思路，可以想到利用 $- 1$ 的幂构造摆动数列，当 $i$ 为奇数时， $1)^i$ 刚好为负数，表示减去奇数项；当 $i$ 为偶数时， $1)^i$ 为正数，尽管有重复计算，可是恰好答案中的每种情况算了两遍，最后除以 $2$ 即可。

$\frac{(r-l+1)^{nm}-\sum_{i=0}^{nm}(-1)^iC_{nm}^{i}a^ib^{nm-i}}{2}$

直接利用二项式定理进行转化，达到复杂度 $O(\log(nm))$ 。

$\frac{(r-l+1)^{nm}-(b-a)^{nm}}{2}$

#include <bits/stdc++.h>
using namespace std;
long long n,m,l,r,mod=998244353;
long long power(long long a,long long p)
{long long x=a,ans=1;while(p){if(p%2==1)ans=ans*x%mod;p/=2;x=x*x%mod;}return ans;
}int main()
{scanf("%lld%lld%lld%lld",&n,&m,&l,&r);if(n*m%2==1)printf("%lld",power(r-l+1,n*m));else {long long a=(r-l+1)/2,b=0;if((r-l+1)%2==1&&l%2==1)a++;b=r-l+1-a;printf("%lld",(power(r-l+1,n*m)+power((b-a+mod)%mod,n*m))%mod*499122177%mod);}return 0;
}

Lucas定理

若 $p$ 为质数，则有如下式子：

$C_n^m\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\times C_{ n\%p }^{m\%p }(mod\;p)$

证明可以看文末的博客。

例题 $5$ ：

P3807 【模板】卢卡斯定理/Lucas 定理

卢卡斯定理模板题，运用卢卡斯定理 $C_n^m\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\times C_{ n\%p }^{m\%p }(mod\;p)$ 把组合数拆成两部分，一部分为 $C_{ n\%p }^{m\%p }$ ，保证了逆元存在，直接用组合求逆元。另一部分 $C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}$ 接着递归就行了。所以，只有 $p$ 为质数时才能使用 Lucas 定理。

注意三个实现细节：

$1$ ： $m = 0$ 时为递归出口，这里应该返回 $1$ 而不是 $0$ 。

$2$ ：可以预处理出阶乘来降低时间复杂度。

$3$ ：当求组合数时如果 $m > n$ 特判返回 $0$ 。

#include <bits/stdc++.h>
using namespace std;
long long t,n,k,m,sum[100010];
long long power(long long a,long long p,long long m)
{long long x=a,ans=1;while(p){if(p%2==1)ans=(x%m*ans%m)%m;p/=2;x=(x%m*x%m)%m;}return ans;
}long long get_c(long long n,long long k,long long m)
{if(k>n)return 0;return ((sum[n]%m*power(sum[k],m-2,m)%m)%m*power(sum[n-k],m-2,m)%m)%m;
}long long lucas(long long n,long long k,long long m)
{if(k==0)return 1;else return (lucas(n/m,k/m,m)%m*get_c(n%m,k%m,m)%m)%m;
}int main()
{scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&n,&k,&m);sum[0]=1;for(int i=1;i<=m;i++)sum[i]=(sum[i-1]%m*i%m)%m;printf("%d\n",lucas(n+k,k,m));}return 0;
}

全排列问题

对于字符集 $X$ ，将 $X$ 的所有元素的可能排列全部枚举出来，对含有 $N$ 个元素的集合 $X$ ，排列总个数 $S$ 为：

$S = N!$

定义一个 $1\sim n$ 的排列 $A$ ，由 $1,2\dots n$ 这 $n$ 个数字组成。

有重复元素的排列

有 $m_1$ 个 $1$ ，有 $m_2$ 个 $2$ ， $\dots$ ，有 $m_k$ 个 $k$ ,
共 $N$ 个元素，排列总个数 $S$ 为：

$S=\frac{N!}{m_1!m_2!\dots m_k!}$

其他杂题

例题 $6$ ：

P3197 [HNOI2008]越狱

由于只要有一种相同宗教相邻就会发生越狱，不好求，可以正难则反，用总共的数量减去没有相邻的数量。

对于总共的情况，由于每一个位置都能选择 $m$ 个宗教，那么根据乘法原理，总共有 $m^n$ 种排列方式。

对于没有相邻的情况，第一个位置有 $m$ 种选择。由于相邻宗教不相同，那么接下来每个位置就有 $m - 1$ 种选择。根据乘法原理，总共有 $m(m-1)^{n-1}$ 种排列方式。

用总共的数量减去不满足的数量，就能得到答案 $S$ 了：

$S=m^n-m(m-1)^{n-1}$

注意减法取模要先加上模数。

#include <bits/stdc++.h>
using namespace std;
long long m,n,mod=100003;
long long power(long long a,long long p,long long m)
{long long x=a,ans=1;while(p){if(p%2==1)ans=ans*x%m;p/=2;x=x*x%m;}return ans;
}int main()
{scanf("%lld%lld",&m,&n);printf("%lld",((power(m,n,mod)-m*power(m-1,n-1,mod))%mod+mod)%mod);return 0;
}

例题 $7$ ：

P4821 [中山市选]生成树

由于生成树中没有环，而每个五边形都构成了一个环，所以每个五边形至少需要拆掉一条边。

而一个五角星圈中间的部分也是一个环，也需要拆掉一条边。所以，会有一个五边形被拆掉两条边。

选择被拆掉两条边的五边形有 $n$ 种选法，拆掉两条边的五边形必须拆掉其在中间部分的边，剩下 $4$ 条边可以任意选择一条拆掉。剩下的 $n - 1$ 个五边形拆掉哪条边没有限制，每个有 $5$ 种拆法，根据乘法原理，共有 $5^{n-1}$ 种。

最后根据乘法原理，得到答案 $S$ 为：

$S=5^{n-1}4n$

#include <bits/stdc++.h>
using namespace std;
int t,n,mod=2007;
int power(int a,int p,int m)
{int x=a,ans=1;while(p){if(p%2==1)ans=ans*x%m;p/=2;x=x*x%m;}return ans;
}int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",4*n%mod*power(5,n-1,mod)%mod);}return 0;
}

递推问题

错排问题

给一个数 $n$ ，求有多少 $1\sim n$ 的排列 $A$ 满足对于每个 $i$ ，都满足 $A_i\ne i$ 。

例如当 $n = 3$ 时，满足要求的排列只有 $2, 3, 1$ 和 $3, 1, 2$ 。

用 $a,b,c,d\dots$ 表示 $n$ 个数字， $A,B,C,D\dots$ 表示 $n$ 个位置（ $a$ 对应 $A$ ），错装的方法总数为记作 $f_n$ 。

假设把 $a$ 错装进 $B$ 中，然后接下来我们可以分为两种情况:

$1$ ： $b$ 错装进了 $A$ 中

那么问题就变为 $c,d\dots$ 个数字（共 $n - 2$ 个）放入 $C,D\dots$ 这 $n - 2$ 个位置时完全装错。由定义得有 $f_{n-2}$ 种。

$2$ ： $b$ 错装进了除 $A$ 之外的一个位置

由于题设中 $b$ 不能放入 $A$ ，我们可以把 $A$ 想象成 $B$ ，就相当于将 $b,c,d\dots$ 这 $n - 1$ 个数字放入 $B,C,D\dots$ 这 $n$ 个位置时完全放错。由定义得有 $f_{n-1}$ 种。

$a$ 错装进 $B$ 中，有 $f_{n-1}+f_{n-2}$ 种，同样 $a$ 错装进 $C$ 中也有 $f_{n-1}+f_{n-2}$ 种 $\dots$ 所以根据加法原理，求出 $f$ 的递推式为：

$f_n=(n-1)(f_{n-1}+f_{n-2})$

例题 $8$ ：

P4071 [SDOI2016]排列计数

由于序列恰好有 $m$ 个位置，使得 $a_i = i$ ，所以剩下的 $n - m$ 个位置满足 $a_i \ne i$ ，就是上文所述的 $f_{n-m}$ ，直接线性递推即可。

使得 $a_i = i$ 的 $m$ 个位置，本身就有 $C_{n}^m$ 种选法。根据乘法原理，得到答案为：

$C_n^mf_{n-m}$

注意需要求逆元以及预处理做到 $O (1)$ 回答询问。

#include <bits/stdc++.h>
using namespace std;
long long t,m,n,cuo[1000020],jc[1000020],inv[1000020],mod=1000000007;
long long power(long long a,long long p,long long m)
{long long ans=1,x=a;while(p){if(p%2==1)ans=ans*x%m;p/=2;x=x*x%m;}return ans;
}int main()
{cuo[0]=1;cuo[2]=1;jc[0]=1;jc[1]=1;inv[0]=1;inv[1]=1;for(int i=2;i<=1000010;i++)jc[i]=jc[i-1]*i%mod;for(int i=2;i<=1000010;i++)inv[i]=power(jc[i],mod-2,mod)%mod;for(int i=3;i<=1000010;i++)cuo[i]=(i-1)*(cuo[i-1]+cuo[i-2])%mod;scanf("%lld",&t);for(int i=1;i<=t;i++){scanf("%lld%lld",&n,&m);if(n<m){printf("0\n");continue;}printf("%lld\n",jc[n]*inv[n-m]%mod*inv[m]%mod*cuo[n-m]%mod);}return 0;
}

第二类Stirling数

$n$ 个有区别的球放到 $m$ 个相同的盒子中，要求无一空盒，其不同的方案数用 $S2_{n,m}$ 表示，称为第二类Stirling数。

设有 $n$ 个不同的球，分别用 $b_1,b_2,\dots b_n$ 表示。从中取出一个球 $b_n$ ， $b_n$ 的放法有以下两种：

$1$ ： $b_n$ 独自占一个盒子

那么剩下的球只能放在 $m - 1$ 个盒子中，方案数为 $S2_{n-1,m-1}$ 。

$2$ ： $b_n$ 与别的球共占一个盒子

那么可以事先将 $b_1,b_2,\dots b_{n-1}$ 这 $n - 1$ 个球放入 $m$ 个盒子中，然后再将球 $bn$ 可以放入其中一个盒子中，方案数为 $mS2_{n-1,m}$ 。

根据加法原理，得出第二类Stirling数的递推式：

$S2_{n,m}=S2_{n-1,m-1}+mS2_{n-1,m}$

例题 $9$ ：

P1655 小朋友的球

第二类Stirling数板子题，注意需要高精度。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int f[101][101][101]; 
void huge_int(int na,int nb,int a,int b,int c,int d,int m)
{int flag=0;for(int i=1;i<=100;i++)f[na][nb][i]=f[a][b][i];for(int i=100;i>0;i--){f[na][nb][i]+=f[c][d][i]*m+flag;flag=f[na][nb][i]/10;f[na][nb][i]%=10;}
}void print(int n,int m)
{int now=1;for(now=1;now<=100;now++)if(f[n][m][now]!=0)break;for(int i=now;i<=100;i++)printf("%d",f[n][m][i]);
}int main()
{for(int i=1;i<=100;i++)f[i][1][100]=f[i][i][100]=1;for(int i=1;i<=100;i++)for(int j=1;j<=100;j++)if(!(i==j||j==1))huge_int(i,j,i-1,j-1,i-1,j,j);while(scanf("%d%d",&n,&m)!=-1){if(n<m){printf("0\n");continue;}print(n,m);putchar('\n');}return 0;
}

后记

教练推荐的几篇博客：

lucas定理

不容易系列之(4)——考新郎

前言

组合计数基础

加法原理与乘法原理

排列与组合

组合数的求法

二项式定理

Lucas定理

全排列问题

全排列问题

有重复元素的排列

其他杂题

递推问题

错排问题

第二类Stirling数

后记

相关文章：