组合数取模

组合数取模的困难不在组合数本身，而在阶乘中的因子能否在当前模数下求逆。

1 从阶乘公式到模意义下的组合数

组合数定义为

$$\binom nr=\frac{n!}{r!(n-r)!},$$

其中 $0\le r\le n$。

在普通整数运算中，分母一定能够整除分子；但在模运算中，除法必须转化为乘法逆元。如果分母与模数不互质，逆元就不存在，阶乘公式不能直接使用。

本章主线：阶乘与逆元 → 模素数下的组合数 → Lucas 定理 → 模质数幂的组合数 → CRT 合并 → ExLucas。

组合数取模的核心是根据模数的结构选择方法：

• 模数为质数时，可以使用逆元；
• $n$ 很大而模数为较小质数时，使用 Lucas；
• 模数为质数幂时，先从阶乘中剥离该质因子；
• 模数为任意合数时，分解为若干质数幂，再用 CRT 合并。

---

2 模质数下的组合数

2.1 阶乘与阶乘逆元

设模数 $p$ 为质数，并且 $n<p$。

由于 $1,2,\ldots,n$ 都不被 $p$ 整除，$n!$、$r!$ 与 $(n-r)!$ 在模 $p$ 下均可逆，因此

$$\binom nr \equiv n!\,(r!)^{-1}\,((n-r)!)^{-1} \pmod p.$$

预处理阶乘 fac 与阶乘逆元 ifac 后，可以在 $O(1)$ 时间内计算一次组合数。

▶

模质数组合数

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

vector<ll> fac, ifac;
ll P;

void init( int N, ll p ) {
    P = p;
    fac.assign( N + 1, 1 );
    ifac.assign( N + 1, 1 );

    for( int i = 1; i <= N; ++ i ) {
        fac[i] = fac[i - 1] * i % P;
    }

    ifac[N] = qpow( fac[N], P - 2, P );
    for( int i = N - 1; i >= 0; -- i ) {
        ifac[i] = ifac[i + 1] * ( i + 1 ) % P;
    }
}

ll nCr( ll n, ll r ) {
    if( n < r || r < 0 ) return 0;
    return fac[n] * ifac[r] % P * ifac[n - r] % P;
}

这套写法要求预处理范围内的阶乘不含模数 $p$，通常使用在 $N<p$ 的情形。

2.2 为什么 $n\ge p$ 时会失效

当 $n\ge p$ 时，$n!$ 含有质因子 $p$，于是

$$n!\equiv0\pmod p.$$

此时阶乘在模 $p$ 下没有逆元，不能直接代入阶乘公式。

但这并不意味着组合数本身一定模 $p$ 为 $0$。例如

$$\binom{p}{1}=p\equiv0\pmod p,$$

而

$$\binom{p}{p}=1.$$

需要进一步分析 $n,r$ 的 $p$ 进制结构，这就是 Lucas 定理处理的问题。

---

3 Lucas 定理

3.1 定理

设 $p$ 为质数，将 $n,r$ 写成 $p$ 进制：

$$n=n_0+n_1p+\cdots+n_kp^k,$$

$$r=r_0+r_1p+\cdots+r_kp^k,$$

其中 $0\le n_i,r_i<p$。

Lucas 定理给出

$$\binom nr \equiv \prod_{i=0}^{k}\binom{n_i}{r_i} \pmod p.$$

若某一位满足 $r_i>n_i$，对应的小组合数为 $0$，因此原组合数模 $p$ 也为 $0$。

3.2 递归形式

取最低位可以得到

$$\binom nr \equiv \binom{n\bmod p}{r\bmod p} \binom{\lfloor n/p\rfloor}{\lfloor r/p\rfloor} \pmod p.$$

不断除以 $p$，就能逐位处理 $n$ 与 $r$。

3.3 为什么能够逐位拆开

在模 $p$ 意义下，由二项式定理有

$$(1+x)^p \equiv1+x^p\pmod p,$$

因为中间的组合数 $\binom pi$ 都是 $p$ 的倍数。

将 $n$ 按 $p$ 进制展开：

$$(1+x)^n = \prod_i(1+x)^{n_ip^i} \equiv \prod_i(1+x^{p^i})^{n_i} \pmod p.$$

比较 $x^r$ 的系数，就得到 Lucas 定理中的逐位乘积。

3.4 实现

▶

Lucas 定理

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

vector<ll> fac, ifac;
ll P;

void init( int N, ll p ) {
    P = p;
    fac.assign( N + 1, 1 );
    ifac.assign( N + 1, 1 );

    for( int i = 1; i <= N; ++ i ) {
        fac[i] = fac[i - 1] * i % P;
    }

    ifac[N] = qpow( fac[N], P - 2, P );
    for( int i = N - 1; i >= 0; -- i ) {
        ifac[i] = ifac[i + 1] * ( i + 1 ) % P;
    }
}

ll nCr( ll n, ll r ) {
    if( n < r || r < 0 ) return 0;
    return fac[n] * ifac[r] % P * ifac[n - r] % P;
}

ll lucas( ll n, ll r ) {
    if( r == 0 ) return 1;

    return nCr( n % P, r % P )
         * lucas( n / P, r / P ) % P;
}

使用这一实现前，需要调用 init(P - 1, P)。

递归层数为 $O(\log_p n)$，但预处理需要 $O(p)$ 时间与空间，所以它适合模数为较小质数的情形。

---

4 阶乘中的质因子个数

4.1 Legendre 公式

设 $p$ 为质数，$v_p(n!)$ 表示 $n!$ 中质因子 $p$ 的指数。

$n!$ 中每个 $p$ 的倍数至少贡献一个 $p$，每个 $p^2$ 的倍数再额外贡献一个 $p$，以此类推，因此

$$v_p(n!) = \left\lfloor\frac np\right\rfloor + \left\lfloor\frac n{p^2}\right\rfloor +\cdots.$$

▶

阶乘中质因子的指数

ll cntp( ll n, ll p ) {
    ll res = 0;

    while( n ) {
        res += n / p;
        n /= p;
    }
    return res;
}

所以组合数中 $p$ 的指数为

$$e= v_p(n!) -v_p(r!) -v_p((n-r)!).$$

若要求模 $p^k$，并且 $e\ge k$，则

$$\binom nr\equiv0\pmod{p^k}.$$

4.2 为什么需要剥离质因子

设模数为 $p^k$。

阶乘中的 $p$ 不可逆，但剥离所有 $p$ 以后，剩余部分一定与 $p^k$ 互质，因此存在逆元。

可以把阶乘写成

$$n!=p^{v_p(n!)}U_p(n),$$

其中 $U_p(n)$ 表示将 $n!$ 中所有质因子 $p$ 剥离后的部分。

于是

$$\binom nr = p^e U_p(n) U_p(r)^{-1} U_p(n-r)^{-1}.$$

接下来的问题变成：如何计算 $U_p(n)\pmod{p^k}$。

---

5 模质数幂的组合数

5.1 去除 $p$ 因子的阶乘

令模数为 $pk=p^k$。

在每个长度为 $pk$ 的区间中，不被 $p$ 整除的数模 $pk$ 形成相同的一组剩余，因此可以按完整周期计算乘积。

对于尾部不足一个周期的部分，再单独枚举。

而所有 $p$ 的倍数在除去一个 $p$ 后，继续形成

$$\left\lfloor\frac np\right\rfloor!$$

中的同类问题，所以还要递归处理 $n/p$。

5.2 单个质数幂下的组合数

▶

模质数幂的组合数

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }
ll inv( ll a, ll mod ) { /* 模板代码略 */ }

ll fac( ll n, ll p, ll pk ) {
    if( n == 0 ) return 1;

    ll res = 1;

    for( ll i = 1; i <= pk; ++ i ) {
        if( i % p != 0 ) {
            res = res * i % pk;
        }
    }

    res = qpow( res, n / pk, pk );

    for( ll i = 1; i <= n % pk; ++ i ) {
        if( i % p != 0 ) {
            res = res * i % pk;
        }
    }

    return res * fac( n / p, p, pk ) % pk;
}

ll cntp( ll n, ll p ) {
    ll res = 0;

    while( n ) {
        res += n / p;
        n /= p;
    }
    return res;
}

ll nCr_pk( ll n, ll r, ll p, ll pk ) {
    if( n < r || r < 0 ) return 0;

    ll a = fac( n, p, pk );
    ll b = fac( r, p, pk );
    ll c = fac( n - r, p, pk );

    ll e = cntp( n, p )
         - cntp( r, p )
         - cntp( n - r, p );

    ll res = a * inv( b, pk ) % pk
               * inv( c, pk ) % pk;

    return res * qpow( p, e, pk ) % pk;
}

这里的 inv 使用扩展欧几里得算法，因为模数 $p^k$ 不一定是质数；剥离 $p$ 后的 a,b,c 都与 $p^k$ 互质，所以逆元存在。

fac 每层需要枚举 $1$ 到 $p^k$，递归深度为 $O(\log_p n)$。因此这份模板适合质数幂 $p^k$ 不太大的情形。

---

6 ExLucas

6.1 从合数模数拆成质数幂

设任意正整数模数 $M$ 的标准质因数分解为

$$M=\prod_{i=1}^{s}p_i^{k_i}.$$

这些质数幂两两互质。

分别计算

$$x_i\equiv\binom nr\pmod{p_i^{k_i}},$$

就得到同余方程组

$$\begin{cases} x\equiv x_1\pmod{p_1^{k_1}},\\ x\equiv x_2\pmod{p_2^{k_2}},\\ \qquad\vdots\\ x\equiv x_s\pmod{p_s^{k_s}}. \end{cases}$$

最后使用 CRT 合并，就能得到 $\binom nr\bmod M$。

6.2 算法结构

ExLucas 可以概括为三个步骤：

1. 将模数 $M$ 分解为若干个质数幂；
2. 对每个 $p_i^{k_i}$ 调用 nCr_pk；
3. 使用 CRT 合并所有余数。

它不是把 Lucas 的递归式简单推广到合数模数，而是组合了质因数分解、模质数幂组合数与 CRT。

6.3 实现

▶

ExLucas

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }
ll inv( ll a, ll mod ) { /* 模板代码略 */ }

ll fac( ll n, ll p, ll pk ) {
    if( n == 0 ) return 1;

    ll res = 1;

    for( ll i = 1; i <= pk; ++ i ) {
        if( i % p != 0 ) {
            res = res * i % pk;
        }
    }

    res = qpow( res, n / pk, pk );

    for( ll i = 1; i <= n % pk; ++ i ) {
        if( i % p != 0 ) {
            res = res * i % pk;
        }
    }

    return res * fac( n / p, p, pk ) % pk;
}

ll cntp( ll n, ll p ) {
    ll res = 0;

    while( n ) {
        res += n / p;
        n /= p;
    }
    return res;
}

ll nCr_pk( ll n, ll r, ll p, ll pk ) {
    if( n < r || r < 0 ) return 0;

    ll a = fac( n, p, pk );
    ll b = fac( r, p, pk );
    ll c = fac( n - r, p, pk );

    ll e = cntp( n, p )
         - cntp( r, p )
         - cntp( n - r, p );

    ll res = a * inv( b, pk ) % pk
               * inv( c, pk ) % pk;

    return res * qpow( p, e, pk ) % pk;
}

ll a[maxn], m[maxn];
ll crt( int cnt ) { /* 模板代码略 */ }

ll exlucas( ll n, ll r, ll mod ) {
    ll tmp = mod;
    int cnt = 0;

    for( ll p = 2; p * p <= tmp; ++ p ) {
        if( tmp % p != 0 ) continue;

        ll pk = 1;
        while( tmp % p == 0 ) {
            pk *= p;
            tmp /= p;
        }

        ++ cnt;
        m[cnt] = pk;
        a[cnt] = nCr_pk( n, r, p, pk );
    }

    if( tmp > 1 ) {
        ++ cnt;
        m[cnt] = tmp;
        a[cnt] = nCr_pk( n, r, tmp, tmp );
    }

    return crt( cnt );
}

这里的 crt 使用 02_同余方程与逆元 中的模板。

该实现使用试除法分解模数，适合模数能够在可接受时间内完成质因数分解的情形。

---

7 方法选择

条件	方法
$n$ 较小，模数为质数，且预处理范围小于模数	阶乘与阶乘逆元
$n,r$ 很大，模数为较小质数	Lucas
模数为质数幂 $p^k$	nCr_pk
模数为任意合数	ExLucas
模数很大且难以试除分解	先使用大整数质因数分解

需要注意：

• Lucas 要求模数是质数；
• 当前 Lucas 模板需要预处理到 $p-1$，因此 $p$ 不能过大；
• 费马逆元只能用于模质数；
• 模 $p^k$ 时必须先剥离阶乘中的所有 $p$；
• ExLucas 中各个质数幂两两互质，所以使用普通 CRT，而不是 ExCRT；
• 当前 fac 的复杂度与 $p^k$ 成正比，质数幂过大时不能直接使用；
• 组合数满足 $\binom nr=0$ 当 $r<0$ 或 $r>n$。

---

8 与前后内容的联系

组合数取模综合使用了前面多章的内容：

• 算术基本定理负责把模数分解成质数幂；
• 逆元负责处理可逆的阶乘部分；
• 费马小定理支持模质数下的阶乘逆元；
• Legendre 公式统计阶乘中的质因子指数；
• CRT 负责合并不同质数幂下的答案；
• 大整数模数的分解可以交给 Miller–Rabin 与 Pollard–Rho。

相关内容：

• 01_整数分解与筛法
• 02_同余方程与逆元
• 04_模意义下的指数问题
• 08_大整数质因数分解