Lucas定理学习笔记

AprilGrimoireLeave a comment

Lucas定理

\binom{n}{m} = \binom{n \mod p}{m \mod p}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}

其中p是质数。

当n和m比较大但p较小时，可以使用Lucas定理快速计算组合数。

证明

\binom{n}{m}的一种意义是(1 + x)^n的m次项系数。在模p意义下，

(1 + x) ^ p = \sum\limits_{i=0}^{n}\binom{n}{i}x^i = 1 + x^p

这是由于\binom{n}{i}在1 \leq i < p时都是p的倍数。

(1 + x) ^ n = (1 + x) ^ {p ^ {\left\lfloor\frac{n}{p}\right\rfloor}} (1 + x) ^ {n \mod p} = (1 + x^p) ^ {\left\lfloor\frac{n}{p}\right\rfloor} (1 + x) ^ {n \mod p}

因此，(1 + x)^n的m次系数一定是由(1 + x^p) ^ {\left\lfloor\frac{n}{p}\right\rfloor}的m \left\lfloor\frac{m}{p}\right\rfloor次系数和(1 + x) ^ {n \mod p}的m \mod p次系数提供的，定理得证。

代码 (BZOJ 2982)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 10007;

int fac[MOD], ifac[MOD];

int sqr(int x) { return x * x % MOD; }

int qpow(int a, int b) { return b ? sqr(qpow(a, b / 2)) * (b & 1 ? a : 1) % MOD : 1; }

int inv(int x) { return qpow(x, MOD - 2); }

void init()
{
    fac[0] = 1;
    for (int i = 1; i < MOD; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MOD - 1] = inv(fac[MOD - 1]);
    for (int i = MOD - 1; i; i--) ifac[i - 1] = ifac[i] * i % MOD;
}

int combs(int a, int b)
{
    if (a < b) return 0;
    return fac[a] * ifac[b] % MOD * ifac[a - b] % MOD;
}

int comb(int a, int b)
{
    return b ? combs(a % MOD, b % MOD) * comb(a / MOD, b / MOD) % MOD : 1;
}

int main()
{
    init();
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++)
    {
        int n, m; scanf("%d%d", &n, &m);
        printf("%d\n", comb(n, m));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注