Lucas定理学习笔记

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是质数。

nm比较大但p较小时,可以使用Lucas定理快速计算组合数。

证明

\binom{n}{m}的一种意义是(1 + x)^nm次项系数。在模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)^nm次系数一定是由(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));
    }
}

发表评论

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