BZOJ 2982 combination

题目大意

求

$$C_n^m \mod 10007 (n,m \le 2 \times 10^9)$$

$$C_n^m = \frac{n!}{m!(n-m)!} = C_{n/p}^{m/p} \times C_{n \mod p}^{m \mod p}$$

Lucas定理就这个。预处理出$\lt 10007$的所有数的阶乘，$n,m \lt 10007$的时候预处理就好了。

时间复杂度$O(\log_p n)$

#include <cstdio>
#include <algorithm>
using namespace std;
#define MO 10007
long long jc[10008]={1},rjc[10008]={1};
long long qpow(long long x,int y)
{
	long long ret=1;
	while(y)
	{
		if(y&1) ret=ret*x%MO;
		x=x*x%MO,y>>=1;
	}
	return ret;
}
long long c(int x,int y)
{
	if(!y) return 1;
	if(x<y) return 0;
	if(x<MO&&y<MO) return jc[x]*rjc[y]*rjc[x-y]%MO;
	return c(x/MO,y/MO)*c(x%MO,y%MO)%MO;
}
int main()
{
	for(int i=1;i<10007;++i) jc[i]=jc[i-1]*i%MO,rjc[i]=qpow(jc[i],MO-2);
	int T,n,m;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%lld\n",c(n,m));
	}
	return 0;
}