前置結(jié)論

如果 \(p\) 為素數(shù),有以下結(jié)論:

1. \(a^p \equiv a \pmod p\)
   即費馬小定理

2. \[C_{p}^i \equiv \begin{cases} 1 & i=0 或者 i=p \\ 0 & 其他情況 \end{cases} \pmod p \]

證明可以展開

3. \((a+b)^p \equiv a^p + b^p \pmod p\)
   證明1：用結(jié)論1
   \[\begin{aligned} (a+b)^p &\equiv a+b \\ &\equiv a^p + b^p \pmod p \end{aligned} \]
   證明2：用結(jié)論2 和 二項式定理
   \[\begin{aligned} (a+b)^p &\equiv \sum_{i=0}^{p} C_{p}^{i} \times a^i \times b^{p-i} \\ &\equiv a^p + b^p \pmod p \end{aligned} \]

Lucas定理

內(nèi)容

$ C_{n}^{m} \equiv C_{\lfloor \frac{n}{p} \rfloor} ^{\lfloor \frac{m}{p} \rfloor} \cdot C_{n \bmod p}^{m \bmod p} \pmod p \text{ p 是 質(zhì)數(shù)}$

用途

當(dāng)質(zhì)數(shù) \(p\) 較小時，求解組合數(shù)在模意義下的值

證明

由二項式定理得:\(C_n^m\) 等于 \((x+1)^n\) 展開后 \(x^m\) 的系數(shù)

所以 \((x+1)^n\) 展開后 \(x^m\) 的系數(shù) = \(\sum (x^p + 1)^{\lfloor \frac{n}{p} \rfloor}\)展開后\(x^{m-r}\)的系數(shù) \(\times (x+1)^{n \bmod p}\)展開后 \(x^r\) 的系數(shù)

容易得到 \(r \le n\bmod p < p\) 并且 \(p \mid (m-r)\) ， 也就是說 \(m\) 可以寫成 \(m=k \times p + r , r<p\) 的形式，根據(jù)帶余除法可知這種表示是唯一的，即只有一個唯一的 \(r\) 和 \(k\) ，其中 $r = m \bmod p,k = \lfloor \frac{m}{p} \rfloor $

所以$ C_{n}^{m} \equiv C_{\lfloor \frac{n}{p} \rfloor} ^{\lfloor \frac{m}{p} \rfloor} \cdot C_{n \bmod p}^{m \bmod p} \pmod p$

代碼實現(xiàn)

【模板】盧卡斯定理/Lucas 定理

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,m,p;
int fac[N],inv[N],q[N];
int C(int n,int m){
	if(m>n) return 0;
	return fac[n]*q[m]%p*q[n-m]%p;
}
int Lucas(int n,int m){
	if(!m) return 1;
	return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read(),p=read();
		fac[0]=1;
		for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;
		inv[1]=1;
		for(int i=2;i<p;i++) inv[i]=inv[p%i]*(p-p/i)%p;
		q[0]=1;
		for(int i=1;i<p;i++) q[i]=q[i-1]*inv[i]%p;
		n=n+m;
		printf("%lld\n",Lucas(n,m));
	}
	return 0;
}

拓展

考慮 \(m,n\) 在 \(p\) 進制下的表示，就會發(fā)現(xiàn) \(C^m_n\) 就等于 \(m,n\) 在 \(p\) 進制下每一位對應(yīng)的組合數(shù)的乘積( \(\bmod\)操作就是取最后一位,\(\lfloor \rfloor\)就是左移一位 ) 。

特殊的，當(dāng) \(p=2\) 時，組合數(shù)有值當(dāng)且僅當(dāng) \(m\) 是 \(n\) 的子集
此時就很高維前綴和 (關(guān)于高維前綴和的知識看這)