【6】组合计数学习笔记

· · 算法·理论

前言

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

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

UPD on 2025.7.19：优化大量格式与内容问题。

组合计数基础

加法原理与乘法原理

加法原理（分类计数原理）：完成一件事有 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，也可以记作 \binom{n}{m}。

组合数计算公式：

C^{m}_n=\binom{n}{m}=\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 ：

*** 由于特殊的两种葵花有特殊要求，应该**优先安排**，以免不合要求的元素占了这四个位置。 先排两盆特殊的葵花有 $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}

考虑 a^kb^{n-k} 是怎么乘出来的。需要在 k 个 (a+b) 的乘积项中选出 k 项贡献 a，然后剩下的项贡献 b。这相当于 n 个元素选出 k 个组合，方案数为 C^k_n。把各项累加起来就是答案。

那么可以推出：

(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 定理。

注意三个实现细节：

$2$ ：可以预处理出阶乘来降低时间复杂度。 $3$ ：当求组合数时如果 $m>n$ 特判返回 $0$ 。 ```cpp #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!}$$ ## 递推问题 ### 错排问题 给一个数 $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})$$ 例题 $6$ ： [P4071 [SDOI2016]排列计数](https://www.luogu.com.cn/problem/P4071) 由于序列恰好有 $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)$ 回答询问。 ```cpp #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}$$ 例题 $7$ ： [P1655 小朋友的球](https://www.luogu.com.cn/problem/P1655) 第二类Stirling数板子题，注意需要高精度。 ```cpp #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; } ``` 如果想了解关于第二类Stirling数的更多内容，可以查看 [【9】斯特林数学习笔记](https://www.luogu.com.cn/article/hpfsgdl8)。 ## 其他杂题 例题 $8$ ： [P3197 [HNOI2008]越狱](https://www.luogu.com.cn/problem/P3197) 由于只要有一种相同宗教相邻就会发生越狱，不好求，可以正难则反，用总共的数量减去没有相邻的数量。 对于总共的情况，由于每一个位置都能选择 $m$ 个宗教，那么根据乘法原理，总共有 $m^n$ 种排列方式。 对于没有相邻的情况，第一个位置有 $m$ 种选择。由于相邻宗教不相同，那么接下来每个位置就有 $m-1$ 种选择。根据乘法原理，总共有 $m(m-1)^{n-1}$ 种排列方式。 用总共的数量减去不满足的数量，就能得到答案 $S$ 了： $$S=m^n-m(m-1)^{n-1}$$ 注意减法取模要先加上模数。 ```cpp #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; } ``` 例题 $9$ ： [P4821 [中山市选]生成树](https://www.luogu.com.cn/problem/P4821) 由于生成树中没有环，而每个五边形都构成了一个环，所以每个五边形至少需要拆掉一条边。 而一个五角星圈中间的部分也是一个环，也需要拆掉一条边。所以，会有一个五边形被拆掉两条边。 选择被拆掉两条边的五边形有 $n$ 种选法，拆掉两条边的五边形必须拆掉其在中间部分的边，剩下 $4$ 条边可以任意选择一条拆掉。剩下的 $n-1$ 个五边形拆掉哪条边没有限制，每个有 $5$ 种拆法，根据乘法原理，共有 $5^{n-1}$ 种。 最后根据乘法原理，得到答案 $S$ 为： $$S=5^{n-1}4n$$ ```cpp #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; } ``` ## 后记 教练推荐的几篇博客： [lucas定理](https://www.cnblogs.com/baihualiaoluan/p/11257478.html) [不容易系列之(4)——考新郎](https://blog.csdn.net/eagle_or_snail/article/details/51356005)