卢卡斯定理 Lucas定理是用来求组合数 (c(n,m) mod p) ，(p) 为素数的值。被用来做大组合数取模。
我们令 (n = sp + q, m = tp + r) ，其中 (q, r < p) ，那么有：
[inom{n}{m} equiv inom{sp+q}{tp+r} equiv inom{s}{t}inom{q}{r} (mod p)
]
求解大组合数取模时，只需继续对 (inom{s}{t}) 递归调用卢卡斯定理。递归边界为 (t = 0) 。
时间复杂度为 (O(plog_p n)) 。
卢卡斯定理证明
首先，我们易得 (inom{p}{f} equiv 0 (mod p)) ，其中 (f > 0, p > f) 。
然后，我们又有：
[egin{split}
(1+x)^n equiv(1+n)^{sp+q} &equiv ((1+x)^p)^s cdot (1+x)^q(mod p) \
&equiv (1+x^p)^scdot (1+x)^q(mod p) \
&equiv sum_{i=0}^s inom{s}{i}x^{icdot p} cdot sum_{j=0}^{q}x^j (mod p)
end{split}]
【注】这里 ((1+x)^p equiv (1+x^p)(mod p)) 是因为 (p) 是质数，它的组合数 (inom{p}{k}) 不会把 (p) 因子消掉，所以一定是 (p) 的倍数。
所以我们有：
[(1+x)^{sp+q} equiv sum_{i=0}^s inom{s}{i}x^{icdot p} cdot sum_{j=0}^{q}x^j (mod p)
]
我们求左边 ((1+x)^{sp+q}) 中的 (x^{tp+r}) 的系数为：(inom{sp+q}{tp+r}) 。
我们求右边 ((1+x)^{tp+r}) 的系数为：(i=t,j=r) 的系数，即：(inom{s}{t}cdot inom{q}{r}) 。
所以有：
[inom{sp+q}{tp+r} equiv inom{s}{t}inom{q}{r} (mod p)
]
得证。
题目
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
ll a[N];
int p, T, n, m;
ll pow(ll y,int z,int p){
y%=p;ll ans=1;
for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
return ans;
}
ll C(ll n,ll m){
if(m>n)return 0;
return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
ll Lucas(ll n,ll m){
if(!m)return 1;
return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int main(){
cin >> T;
while(T--){
cin >> n >> m >> p;
a[0]=1;
for(int i = 1; i <= p; i++) a[i] = (a[i - 1] * i) % p;
cout << Lucas(n + m, n) << endl;
}
}