Lucas定理

Lucas可以解决组合数求模的问题。

当要求的组合数比较大，而且对一个素数取模时。

普通的递推或者逆元的方法都不适用了。只能借助于Lucas定理。

\[C_{n}^{m} \% p \]

\[ C(n,m)=C([n/p],[m/p]) * C(n\%p,m\%p) (mod p) \] 具体证明，网上很多版本，就不给出了。 HDU3037 模板题。 m个要分给n个树。树是不一样的。加一个空的，表示不放的。将不大于m颗种子存放在n颗树中，问有多少种存法。这样就是 \( x_{1} + x{2} + …… + x_{n+1} = m \) 的非负整数解个数。答案就是 C(n+m,n)

/* ***
Author :kuangbin
Created Time :2014/7/9 23:18:55
File Name :E:\2014ACM\专题学习\数学\Lucas定理\HDU3037.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
long long F[100010];
void init(long long p)
{
F[0] = 1;
for(int i = 1;i <= p;i++)
F[i] = F[i-1]i%p;
}
long long inv(long long a,long long m)
{
if(a == 1)return 1;
return inv(m%a,m)(m-m/a)%m;
}
long long Lucas(long long n,long long m,long long p)
{
long long ans = 1;
while(n&&m)
{
long long a = n%p;
long long b = m%p;
if(a < b)return 0;
ans = ans*F[a]%p*inv(F[b]*F[a-b]%p,p)%p;
n /= p;
m /= p;
}
return ans;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n,m,p;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d%d”,&n,&m,&p);
init(p);
printf(“%d\n”,(int)Lucas(n+m,n,p));
}
return 0;
}