组合数漫谈

排列与组合

在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。

排列数

从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有排列的个数,叫做从 n 个不同元素中取出 m 个元素的排列数,用符号 A(n,m)表示。

组合数

从 n 个不同元素中,任取 m 个元素并成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合;从 n 个不同元素中取出 m 个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数。用符号 C(n,m) 表示。

组合数也常用 表示,即 (注意他们是上下颠倒的)这个符号其实称作二项式系数的符号,与下文二项式定理有关。

另外,我们认为当 时,

多重集的排列数

多重集是指包含重复元素的广义集合。设 表示由 ,…, 组成的多重集,S 是全排列个数为

相当于把相同元素的排列数除掉了。

多重集的组合数 1

表示由 ,…, 组成的多重集。那么对于整数 ,从 S 中选择 r 个元素组成一个多重集的数量是

这其实是一个超级弱化版的多重集组合数。证明就是插板法。

多重集的组合数 2

上述推论的 r 的范围太过局限。而我们知道对于所取的数是有限制的。假设我们取 ,那么显然有

而我们总共取 r 个,意味着

本质上我们要求这个方程的非负整数解的个数。于是很自然地想到了容斥原理。容斥的模型如下:

  1. 全集: 的非负整数解
  2. 属性:

于是设满足属性 i 的集合是 表示不满足属性 i 的集合,即满足 的集合。那么答案即为

一个赤裸裸的容斥!于是得到

于是拿全集 减去上式,得到多重集的组合数为

其中 A 是充当枚举子集的作用,满足

二项式定理

好吧,多重集组合数扯得有点远了。来讲一个家喻户晓的东西。二项式定理就是一个展开式:

证明?数学归纳法。本质就是利用了 做归纳。

一些推论

接下来介绍一些和组合数相关的推论与扩展。

关于二项式定理的扩展

,得到

得到

关于组合数的推论

我们知道 ,那么可以推出这样两个结论:

简单来说,底数与顶数同时递增,或者底数递增的组合数求和式子是可以合并的。

怎么证明?差分。也叫裂项。

,于是推出

于是这就变成了与 i 和 i-1 有关的式子。算一下求和式子就发现中间的都抵消了。

对于第而个式子,我们有 ,于是得到

于是这又是一个裂项相消的式子。

计算组合数

Subtask1

时间复杂度

Subtask2

是质数。

费马小定理求逆元,将除法转化为乘法即可。

时间复杂度

Subtask3

, 是质数。

lucas 定理:p 为质数时,

转化为 Subtask2,时间复杂度

Subtask4

分解质因数:

中,质因子 p 的出现次数为:

则在 中 p 出现的次数为 。最后剩下的质数相乘即可。

复杂度

Subtask5

,求

Subtask6

是质数。

先Lucas,然后分块打表。

设块大小为T,大力打个表计算 ,打完表后,计算 的复杂度就是 的。空间复杂度

, 则时空复杂度为

LG2822 组合数问题

分解质因数

对于一个 ,统计 中的幂次数。

同理,求出分子分母的 幂次差,可判断能否被 整除。因此对于一个组合数的判断,复杂度

然后矩阵前缀和从 推到 即可

总复杂度 .

#include<cstdio>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=2003,M=2003;
int t,k,ans,n,m;
int p[20],c[20],cnt;// 分解质因数
int sum[N][M];//sum[i,j]:n=i,m=j 时的解
bool v[N][M];
int f(int x,int p){//x! 含有 p 的幂次数
    int res=0;
    while(x)res+=x/p,x/=p;
    return res;
}
int F(int a,int b){
    if(a*b==0)return 0;//1%k!=0
    if(a<b)return F(a,a);
    if(v[a][b])return sum[a][b];
    sum[a][b]=v[a][b]=1;
    FOR(i,1,cnt)sum[a][b]&=(f(b,p[i])+f(a-b,p[i])+c[i]<=f(a,p[i]));
    sum[a][b]+=F(a,b-1)+F(a-1,b)-F(a-1,b-1);// 矩阵前缀和
    return sum[a][b];
}
int main(){
    scanf("%d%d",&t,&k);
    for(int i=2;i*i<=k;i++){
        if(k%i==0)cnt++,p[cnt]=i;
        while(k%i==0)c[cnt]++,k/=i;
    }
    if(k!=1)p[++cnt]=k,c[cnt]++;// 分解质因数
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",F(n,m));
    }
    return 0;
}

Lucas 定理

用于求解 (p 是质数)的问题。

LG3807 卢卡斯定理

就这道题的数据范围还用不到 Lucas

不过鉴于是模板,姑且用一用。

原理是

费马小定理求逆元即可

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,p;
int ksm(int a,int x){
    int res=1;
    while(x){
        if(x&1)res=(long long)res*a%p;
        a=(long long)a*a%p,x>>=1;
    }
    return res;
}
int c(int a,int b){
    if(a>p||b>p)return c(a/p,b/p)*c(a%p,b%p)%p;
    if(a<b)return 0;
    if(b==0)return 1;
    b=min(b,a-b);
    int ps=1,qs=1;
    for(int i=a;i>a-b;i--)ps=(long long)ps*i%p;
    for(int i=1;i<=b;i++)qs=(long long)qs*i%p;
    qs=ksm(qs,p-2);
    return (long long)ps*qs%p;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&p);
        printf("%d\n",c(n+m,m));
    }
    return 0;
}

NOIP2011 计算系数

组合数可以 递推

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int P=10007;
int a,b,k,m,n,ans=1;
int C[1003][1003];
int c(int x,int y){
    return y>x?0:(y==0?1:(C[x][y]?C[x][y]:(C[x][y]=(c(x-1,y-1)+c(x-1,y))%P)));
}
signed main(){
    scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);
    a%=P,b%=P;
    for(int i=1;i<=n;i++)ans=ans*a%P;
    for(int i=1;i<=m;i++)ans=ans*b%P;
    printf("%lld",c(k,n)*ans%P);
    return 0;
}

SP5973 SELTEAM - Selecting Teams

n 个人里面选 k 个人的方案数为 ,则 k 个人中选一个做队长,剩下的人有 种选法,答案即为

,进一步简化代码;

#include<bits/stdc++.h>
#define P 8388608
using namespace std;
typedef long long ll;
ll T,n,k,c[100001][30];
ll C(ll a,ll b){
    if(a<b)return 0;
    if(b==0)return 1;
    if(c[a][b])return c[a][b];
    return c[a][b]=(C(a-1,b-1)%P+C(a-1,b)%P)%P;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(k>24)k=24;
        ll sum=0;
        for(ll m=1;m<=k;m++){
            sum+=(C(n,m)*m%P)*((1<<(m-1))%P)%P;
            sum%=P;
        }
        printf("%d\n",sum);
    }
    return 0;
}

SCOI2010 生成字符串

在坐标系中,把 1 当做向右 1 单位,0 当作像上 1 单位

如果一个字符串中 0 的个数多余 1 的个数,则有 ,则 必在 的上方

即题目要求从 走到 ,不走到 上方的情况下的方案数

如果不考虑 01 的个数,则从 走到 的方案数为 .

接下来考虑走到 上方的方案数

我们将 沿 翻折到 ,如果你走到了 ,那么你必然走到了 的上方;把路径翻折回去,就是走到 上方的一条路径;方案数为 .

于是答案即为 .

#include<cstdio>
#include<algorithm>
using namespace std;
const int P=20100403;
int n,m;
int ksm(int a,int m){
    int res=1;
    while(m){
        if(m&1)res=(long long)res*a%P;
        a=(long long)a*a%P,m>>=1;
    }
    return res;
}
int c(int a,int b){
    if(b>a)return 0;
    b=min(b,a-b);
    int res=1,p=1;
    for(int i=a-b+1;i<=a;i++)res=(long long)res*i%P;
    for(int i=1;i<=b;i++)p=(long long)p*i%P;
    res=(long long)res*ksm(p,P-2)%P;
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    printf("%d",((c(n+m,m)-c(n+m,m-1))%P+P)%P);
    return 0;
}

  转载请注明: Sshwy's Blog 组合数漫谈

 上一篇
二分图漫谈 二分图漫谈
二分图一个无向连通图 中存在 满足 $\forall x,y\in B
2018.12.21
下一篇 
卡特兰数 -Catalan 卡特兰数 -Catalan
卡特兰数又称卡塔兰数,英文名 Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁 · 查理 · 卡塔兰 (1814–1894) 的名字来命名。 计算 \begin{split} &T_0=
2018.12.21
  目录