BZOJ2982: combination Lucas模板

2982: combination

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 734 Solved: 437
[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

Sample Output

5
10
35
6

HINT

Source

lucas模板题

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <map>
 9 #include <string> 
10 #include <cmath> 
11 #include <sstream>
12 #define min(a, b) ((a) < (b) ? (a) : (b))
13 #define max(a, b) ((a) > (b) ? (a) : (b))
14 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
15 template<class T>
16 inline void swap(T &a, T &b)
17 {
18     T tmp = a;a = b;b = tmp;
19 }
20 inline void read(long long &x)
21 {
22     x = 0;char ch = getchar(), c = ch;
23     while(ch < '0' || ch > '9') c = ch, ch = getchar();
24     while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
25     if(c == '-') x = -x;
26 }
27 const long long INF = 0x3f3f3f3f;
28 const long long MAXN = 200000000;
29 const long long MOD = 10007;
30 
31 long long f[MOD + 1000], t, n, m;
32 long long pow(long long a, long long b)
33 {
34     long long r = 1, base = a % MOD;
35     for(;b;b >>= 1)
36     {
37         if(b & 1) r *= base, r %= MOD;
38         base *= base, base %= MOD;
39     }
40     return r;
41 }
42 long long ni(long long x)
43 {
44     return pow(x, MOD - 2);
45 }
46 long long C(long long n, long long m)
47 {
48     if(n < m) return 0;
49     int tmp = f[n] * ni(f[m]) % MOD , tmp2 = tmp * ni(f[n - m]) % MOD;
50     return tmp2;
51 }
52 long long lucas(long long n, long long m)
53 {
54     if(!m) return 1;
55     else return C(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;
56 }
57 
58 int main()
59 {
60     read(t);f[0] = 1;
61     for(long long i = 1;i <= MOD;++ i)
62         f[i] = f[i - 1] * i % MOD;
63     for(long long i = 1;i <= t;++ i)
64     {
65         read(n), read(m);
66         printf("%lld
", lucas(n, m));
67     }
68     return 0;
69 }

BZOJ2982