题面戳我

Solution

• 板子题

Code

//It is coded by ning_mew on 7.25

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const LL MOD=10007;

int T;

LL A[MOD],B[MOD],n,m;

void pre(){

	A[0]=B[0]=A[1]=B[1]=1;

	for(int i=2;i<MOD;i++)B[i]=-(MOD/i)*B[MOD%i]%MOD;

	for(int i=2;i<MOD;i++)A[i]=i*A[i-1]%MOD,B[i]=B[i]*B[i-1]%MOD;

	return;

}

LL C(LL n,LL m){

	if(m>n)return 0;

	return A[n]*B[n-m]%MOD*B[m]%MOD;

}

LL Lucas(LL n,LL m){

	if(m==0)return 1;

	return Lucas(n/MOD,m/MOD)*C(n%MOD,m%MOD)%MOD;

}

int main(){

	pre();

	scanf("%d",&T);

	for(int i=1;i<=T;i++){

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

		printf("%lld\n",(Lucas(n,m)%MOD+MOD)%MOD);

	}return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会场场比赛暴0！！！