【数学】组合数的计算

更新于 分类于 ， 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

组合数的计算方法（递推、消分母分子、阶乘+逆元、卢卡斯定理）

递推

1
2
3
4
5
6
void init() {
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j <= i; ++j)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
}

消分母分子

1
2
3
4
5
6
7
8
ll C(ll n,ll k)
{
    if(2*k>n) k=n-k;
    ll s=1;
    for(ll i=1,j=n; i<=k; i++,j--)
        s=s*j/i;
    return s;
}

预处理阶乘+逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fac[N],inv[N]; // 阶乘和阶乘逆元
void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2); // 快速幂
    for(int i=n-1;i>=0;i--)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
// 求C(x,y)
int C(int x,int y)
{
    if(x<y || y<0)return 0;
    return 1ll*fac[x]*inv[x-y]%mod*inv[y]%mod;
}

卢卡斯定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义求解
int C(int a, int b, int mod) {
    if (b > a) return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; ++i, --j) {
        res = (ll)res * j % mod;
        res = (ll)res * qpow(i, mod - 2) % mod;
    }
    return res;
}

int lucas(ll a, ll b, ll mod) {               // 注意ll参数类型
    if (a < mod && b < mod) return C(a, b, mod);
    return (ll)C(a % mod, b % mod, mod) * lucas(a / mod, b / mod, mod) % mod;     // 递归让其到mod范围内求解
}

其他内容

x<4×1012x<4\times 10^{12}，最多有1111 个不同的质因子

F(a,b)=∑m=0bC(a,m)，F(a,b)=2×F(a−1,b)−C(a−1,b)F(a,b)=\sum_{m=0}^{b}C(a,m)，F(a,b)=2\times F(a-1,b)-C(a-1,b)

2×F(a−1,b)=C(a−1,0)×2+C(a−1,1)×2+C(a−1,2)×2+...C(a−1,b)×2=C(a,0)+C(a,1)+C(a,2)+C(a,3)+...+C(a,b)+C(a−1,b)=F(a,b)+C(a−1,b)\begin{aligned} 2\times F(a-1,b)&=C(a-1,0)\times 2+C(a-1,1)\times 2+C(a-1,2)\times 2+...C(a-1,b)\times 2\\&=C(a,0)+C(a,1)+C(a,2)+C(a,3)+...+C(a,b)+C(a-1,b)\\&=F(a,b)+C(a-1,b)\end{aligned}