组合数学 P3807 【模板】卢卡斯定理 / Lucas 定理 (nm) mod p=(⌊np⌋⌊mp⌋)⋅(n mod pm mod p) mod p\begin{aligned} \begin{pmatrix} n \ m \end{pmatrix} \ mod \ p = \begin{pmatrix} \lfloor \frac{n}{p} \rfloor \ \lfloor \frac{m}{p} \rfloor \end{pmatrix} \cdot \begin{pmatrix} n\ mod\ p \ m\ mod\ p \end{pmatrix} \ mod \ p \ \ \end{aligned} 证明略，网上一堆。代码： #include using namespace std; #define int long long const int N=1e5+5; int T; int inv[N],ninv[N]; int qpow(int x,int y,int mod){ int res=1; while(y){ if(y&1) (res*=x)%=mod; y>>=1,(x*=x)%=mod; } return res; } int C(int n,int m,int mod){ if(m>n) return 0; return inv[n]*ninv[m]%mod*ninv[n-m]%mod; } int lucas(int n,int m,int mod){ if(m==0) return 1; return C(n%mod,m%mod,mod)*lucas(n/mod,m/mod,mod)%mod; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; while(T--){ int n,m,mod; cin>>n>>m>>mod; inv[0]=1; for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; int T; int inv[N],ninv[N]; int qpow(int x,int y,int mod){ int res=1; while(y){ if(y&1) (res*=x)%=mod; y>>=1,(x*=x)%=mod; } return res; } int C(int n,int m,int mod){ if(m>n) return 0; return inv[n]*ninv[m]%mod*ninv[n-m]%mod; } int lucas(int n,int m,int mod){ if(m==0) return 1; return C(n%mod,m%mod,mod)*lucas(n/mod,m/mod,mod)%mod; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; while(T--){ int n,m,mod; cin>>n>>m>>mod; inv[0]=1; for(int i=1;i inv[i]=inv[i-1]*i%mod; ninv[i]=qpow(inv[i],mod-2,mod); } coutlucas(n+m,n,mod)"\n"; } return 0; }`
组合数学
笔记