C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 376K, 提交时间: 2023-03-22 14:15:15

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e4+7;
int t;
int n,m;
inline int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ret%mod;
}
inline int C(int a,int b){
    if(b>a) return 0;
    int x=1,y=1;
    for(int i=a-b+1;i<=a;++i) x=x*i%mod;
    for(int i=1;i<=b;++i) y=y*i%mod;
    return x*ksm(y,mod-2)%mod;
}
inline int lucas(int a,int b){
    if(!b) return 1;
    else return C(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}
signed main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        int l=lucas(n,m);
        cout<<l<<endl;
    }
    
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2020-02-14 15:03:30

#include<cstdio>
#define mod 10007
int fac[10010];
int pow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ans;
}
int cal(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*pow(fac[m],mod-2)%mod*pow(fac[n-m],mod-2)%mod;

}
int lucas(int n,int m)
{
	if(!m) return 1;
	return cal(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
	int t,n,m,i;
	scanf("%d",&t);
	fac[0]=1;
	for(i=1;i<mod;i++) fac[i]=fac[i-1]*i%mod;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",lucas(n,m));
	 } 
	 return 0;
}