G27 求组合数 卢卡斯定理

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const LL P=10007;
LL fac[11100];
LL qpow(LL a,LL b)
{
	LL ans=1%P;a%=P;
	for(;b>0;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;
	return ans;
}
LL C(LL n,LL m)
{
	return (n<m) ? 0ll :fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;
}
LL Lucas(LL n,LL m)
{
	return (m==0) ? 1ll :C(n%P,m%P)*Lucas(n/P,m/P)%P;
}
int main()  
{
	LL T,n,m;cin>>T;
	fac[0]=1;for(int i=1;i<=P;i++)fac[i]=fac[i-1]*i%P;
	while(T--)
	{
		cin>>n>>m;
		cout<<Lucas(n,m)<<"\n";
	}
	return 0;  
}

G27 求组合数 卢卡斯定理

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const LL P=10007;
LL fac[11100];
LL qpow(LL a,LL b)
{
	LL ans=1%P;a%=P;
	for(;b>0;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;
	return ans;
}
LL C(LL n,LL m)
{
	return (n<m) ? 0ll :fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;
}
LL Lucas(LL n,LL m)
{
	return (m==0) ? 1ll :C(n%P,m%P)*Lucas(n/P,m/P)%P;
}
int main()  
{
	LL T,n,m;cin>>T;
	fac[0]=1;for(int i=1;i<=P;i++)fac[i]=fac[i-1]*i%P;
	while(T--)
	{
		cin>>n>>m;
		cout<<Lucas(n,m)<<"\n";
	}
	return 0;  
}