Lucas定理

  Lucas(n,m,p)=c(n%p,m%p)* Lucas(n/p,m/p,p),其中lucas(n,m,p)=C(n,m)%p

  (这里的除号是整除)

证明——百度百科

hdu3037 Lucas定理-LMLPHP

题意:求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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f using namespace std; long long fac[]; long long quick(long long a, long long n, long long p)
{
long long tmp=a%p, ret=;
while(n)
{
if(n&)
ret=(ret*tmp)%p;
tmp=(tmp*tmp)%p;
n>>=;
}
return ret%p;
} long long C(long long n, long long m, long long p)
{
if(m>n) return ;
fac[]=;
for(int i=; i<=n; i++)
fac[i]=(fac[i-]*i)%p;
return (fac[n]*quick(fac[m]*fac[n-m], p-, p))%p;
} long long Lucas(long long n, long long m, long long p)
{
long long ret=;
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 ;
}
04-27 06:05