http://www.lydsy.com/JudgeOnline/problem.php?id=2982
T行,每行一个数,为C(n, m) mod 10007的答案。(1<=m<=n<=200,000,000)
View Code
/************************************************************** Problem: 2982 User: huhuuu Language: C++ Result: Accepted Time:236 ms Memory:1272 kb ****************************************************************/ #include<iostream> #include<stdio.h> using namespace std; int pow_mod(int a,int n,int p) { int ans=1,t=a; while(n) { if(n&1) ans=(long long)ans*t%p; t=(long long)t*t%p; n>>=1; } return ans; } int cal(int n,int m,long p) { if(m>n-m) m=n-m; int ans=1; for(int i=1;i<=m;i++) { ans=(long long)ans*(n-i+1)%p; int a=pow_mod(i,p-2,p); ans=(long long)ans*a%p; } return ans; } int com_mod(int n,int m,long p) { if(n<m)return 0; return cal(n,m,p); } int lucas(int n,int m,long p) { int r=1; while(n&&m&&r) { r=(long long)r*com_mod(n%p,m%p,p)%p; n/=p; m/=p; } return r; } int main() { int t; scanf("%d",&t); while(t--) { int n,m,p; scanf("%d%d",&n,&m);p=10007; printf("%d\n",lucas(n,m,p)); } }