BZOJ 2982 combination Lucas定理

题目大意：发上来就过不了审核了……总之大意就是求C(n,m) mod 10007 m,n∈[1,2*10^8]

卢卡斯定理：C(n,m)=C(n%p,m%p)*C(n/p,m/p) mod p 要求p是质数

当中n%p可能会小于m%p 这样的情况下直接返回0就可以

证明去问卢卡斯 我不知道

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define p 10007

using namespace std;

int fac[p],inv[p];

void Linear_Shaker()

{

	int i;

	fac[0]=1;

	for(i=1;i<p;i++)

		fac[i]=fac[i-1]*i%p;

	inv[1]=1;

	for(i=2;i<p;i++)

		inv[i]=(p-p/i)*inv[p%i]%p;

	inv[0]=1;

	for(i=1;i<p;i++)

		inv[i]=inv[i]*inv[i-1]%p;

}

int C(int n,int m)

{

	if(n<m)

		return 0;

	if(n<p&&m<p)

		return fac[n]*inv[m]%p*inv[n-m]%p;

	return C(n%p,m%p)*C(n/p,m/p)%p;

}

int main()

{

	int T,n,m;

	Linear_Shaker();

	for(cin>>T;T;T--)

	{

		scanf("%d%d",&n,&m);

		printf("%d\n",C(n,m));

	}

}