lucas裸题. C(m,n) = C(m/p,n/p)*C(m%p,n%p).
-----------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 10007;
int Inv[MOD], fac[MOD], N, M;
void gcd(int a, int b, int &d, int &x, int &y) {
if(!b) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
int INV(int v) {
int d, x, y;
gcd(v, MOD, d, x, y);
return (x + MOD) % MOD;
}
void Init() {
fac[0] = 1;
for(int i = 1; i < MOD; i++)
fac[i] = i * fac[i - 1] % MOD;
for(int i = 0; i < MOD; i++)
Inv[i] = INV(fac[i]);
}
int C(int m, int n) {
if(m > n) return 0;
return fac[n] * Inv[m] % MOD * Inv[n - m] % MOD;
}
int Lucas(int m, int n) {
int ret = 1;
while(m) {
(ret *= C(m % MOD, n % MOD)) %= MOD;
n /= MOD;
m /= MOD;
}
return ret;
}
int main() {
Init();
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &N, &M);
printf("%d\n", Lucas(M, N));
}
return 0;
}
-----------------------------------------------------------------------------------------
2982: combination
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 245 Solved: 153
[Submit][Status][Discuss]
Description
LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
Input
第一行一个整数t，表示有t组数据。(t<=200)
接下来t行每行两个整数n, m，如题意。
Output
T行，每行一个数，为C(n, m) mod 10007的答案。
Sample Input
4
5 1
5 2
7 3
4 2
5 1
5 2
7 3
4 2
Sample Output
5
10
35
6
10
35
6