组合数

基础

\(C(^n_m)\)表示从n个东西中选m个的方案数

\(C(^n_m)=\frac{n!}{m!(n-m)!}\)

多项式系数

\((a+b)^n=\sum\limits_{i=0}^n{(^n_i)a^ib^{n-i}}\)

一些知识

\(\sum\limits_{i=0}^n(^n_i)=2^n\)其实就相当于从n个物品中选任意多个物品的方案数。枚举每个物品选不选

\(\sum\limits_{i=0}^k{(^{n+i-1}_i)}=(^{n+k}_k)\)

计算——杨辉三角

\((^n_m)\)与杨辉三角第n行第m列(从0开始计数)相同，n方预处理。适合1000以内的组合数

复杂度:\((O(n^2))\)

void pre(int n) {
    C[0][0]=1;
    for(int i=1;i<=n;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j) {
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}

计算——分解质因数

\((^n_m)=\frac{n!}{n!(n-m)!}=\frac{n(n-1)(n-2)...(n-m+1)}{m(m-1)(m-2)...(1)}=\prod\limits_{i=1}^m{\frac{n+1-i}{i}}\)

对于分子分母分别分解质因数，然后将质因数相减求和。

分解质因数的方法，用cnt[i]表示分子分解后i出现了多少次，用线性筛求出每个合数的最小质因数用mnp[i]表示，从大往小扫，对于每个数，cnt[i]++,对于合数\(cnt[mnp[i]]+=cnt[i],cnt[i/mnp[i]]+=cnt[i]\)，同样方法处理处分母的质因数。

复杂度：\((O(n))\)

void fj(int n) {//线性筛 
    for(int i=2; i<=n; ++i) {
        if(!vis[i]) {
            dis[++dis[0]]=i;
            mnp[i]=i;
        }
        for(int j=1; j<=dis[0]&&dis[j]*i<=n; ++j) {
            vis[dis[j]*i]=1;
            mnp[dis[j]*i]=dis[j];
            if(i%dis[j]==0) break;
        }
    }
}
ll qmi(ll x,int y) {//快速幂 
    ll ans=1;
    for(ll now=x; y; y>>=1,now=now*now%mod)
        if(y&1) ans*=now,ans%=mod;
    return ans;
}
int CC(int n,int m) {
    for(int i=n; i>=n-m+1; --i) {//分解分子 
        cnt[i]++;
        if(vis[i]) cnt[mnp[i]]+=cnt[i],cnt[i/mnp[i]]+=cnt[i];
    }
    for(int i=n-m; i>=1; --i)
        if(vis[i])  cnt[mnp[i]]+=cnt[i],cnt[i/mnp[i]]+=cnt[i];
    for(int i=m; i>=1; --i) {//分解分母 
        cnt2[i]++;
        if(vis[i]) cnt2[mnp[i]]+=cnt2[i],cnt2[i/mnp[i]]+=cnt2[i];
    }
    ll ans=1;
    for(int i=1; i<=dis[0]; ++i) {//计算 
        ans*=qmi(dis[i],(cnt[dis[i]]-cnt2[dis[i]])%mod);
        ans%=mod;
    }
    return ans;
}

计算——卢卡斯定理

对于n比较大，mod比较小的情况且mod为质数。可以讲m和n拆分为p进制的数。

\(n=n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0\)

\(m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0\)

那么\((^n_m)=\prod\limits_{i=0}^k{(^{n_i}_{m_i})}\)

ll jc[N],inv[N];
ll calc(int n,int m) {
    if(n<m) return 0;
     if(n<=mod) return jc[n]*inv[jc[m]]%mod*inv[jc[n-m]]%mod;
     return calc(n/mod,m/mod)*calc(n%mod,m%mod)%mod;
} 
ll lucas(int n,int m) {
    jc[1]=jc[0]=inv[1]=inv[0]=1;
    for(int i=2;i<=mod;++i) jc[i]=jc[i-1]*i%mod;
    for(int i=2;i<=mod;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    return calc(n,m);
}

前缀和

\(\sum\limits_{i=0}^n{(^i_m)}=(^{n+1}_{m+1})\)

\(\sum\limits_{i=0}^m{(^n_i)}=Sum(n,m)\)

\(sum(n,m)\)可以递推

\(sum(n,m)=sum(n,m-1)-(^n_m)\)

\(sum(n+1,m)=2sum(n,m)-(^n_m)\)

组合意义

1.从n个元素中选k项共有\((^n_k)\)种方式

2.从一个n元素集合中选取k元素(可重复选取)构成多重集共有\((^{n+k-1}_k)\)种方式。

3.共有\((^{n+k}_k)\)个字符串包含k个0和n个1

4.共有\((^{n+1}_k)\)个字符串包含k个0和n个1

5.卡特兰数为\(\frac{(^{2n}_n)}{n+1}\)

6.一个网格纸，每次只能往上或往右走，从(0,0)走到(n,m) 的方案数是\((^{n+m}_m)=(^{n+m}_n)\)。类似的从(a,b)走到(c,d)的方案数是\((^{c-a+d-b}_{a-c})=(^{c-a+d-b}_{d-b})\)

7.方程\(\sum\limits_{i=1}^m{x_i}=N　(x_i\geqslant 0)\)的解的个数是\((^{n+m-1}_{m-1})\)

容斥原理

\(|A\cup B|=|A|+|B|-|A\cap B|\)

\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\)

第二类斯特林数

将n个有标号的球放到m个无标号的盒子里，不能有空盒，所有的方案数\(\{^n_k\}\)就是第二类斯特林数

递推式:考虑最后一个球是单独放到一个盒子里还是与前面的球放到同一个盒子里。\(\{^n_k\}=k\{^{n-1}_k\}+\{^{n-1}_{k-1}\}\)

卡特兰数

递推式:\(C_{n+1}=\sum\limits_{i=0}^{n-1}C_iC_{n-i}\)

经典应用：

1.问由2n个括号组成的合法的括号序列的个数。考虑用左括号表示进栈，右括号表示出栈。当栈空时表示前面形成一个合法序列。然后枚举栈空的位置，加入在k位置栈空，那么前面和后面都必须是合法序列，就是\(C_kC_{n-k}\)。然后k可以使0到n中的任何一个位置，所以答案就是\(C_n\)

2.在\(n*n\)的网格图中，从(0,0)到(n,n)不穿过对角线的单调路径的个数

如图所示，可以枚举触碰到对角线的位置，将向上走表示为进栈，向右走表示为出栈，那么碰到对角线的时候就是栈空的时候，和上题就类似了。