本文共 1417 字，大约阅读时间需要 4 分钟。
Lucas定理
Lucas(n,m,p)=c(n%p,m%p)* Lucas(n/p,m/p,p)，其中lucas(n,m,p)=C(n,m)%p
(这里的除号是整除)
证明——百度百科
题意：求n个数的和<=m的方案数
题解：
求a1+a2+ ... +an=m方案数, 利用隔板法要使得每个数>=1，所以令bi = ai+1>=1 则 b1+b2+ ... +bn=m+n方案数为C(m+n-1, n-1)=C(m+n-1, m)
故 ans = sigama(C(i+n-1, i)) = C(n-1, 0) + C(n, 1) + C(n+1, 2) + ... + C(n+m-1, m) = C(n+m, m)
剩下的就是Lucas定理的应用了。
#include #include #include #include #include #include #include #include #include #include #include #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3fusing namespace std;long long fac[100005];long long quick(long long a, long long n, long long p){ long long tmp=a%p, ret=1; while(n) { if(n&1) ret=(ret*tmp)%p; tmp=(tmp*tmp)%p; n>>=1; } return ret%p;}long long C(long long n, long long m, long long p){ if(m>n) return 0; fac[0]=1; for(int i=1; i<=n; i++) fac[i]=(fac[i-1]*i)%p; return (fac[n]*quick(fac[m]*fac[n-m], p-2, p))%p;}long long Lucas(long long n, long long m, long long p){ long long ret=1; while(n && m) { ret=ret*C(n%p, m%p, p)%p;//注意 C(10, 8) % 9这类情况 n/=p; m/=p; } return ret;}long long n,m,p;int main(){ int t; scanf("%d", &t); while(t--) { scanf("%I64d%I64d%I64d", &n, &m, &p); printf("%I64d\n", Lucas(n+m, m, p)); } return 0;}
转载于:https://www.cnblogs.com/Mathics/p/4006253.html
