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模板题

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #include <map>

 #include <string>

 #include <cmath>

 #include <sstream>

 #define min(a, b) ((a) < (b) ? (a) : (b))

 #define max(a, b) ((a) > (b) ? (a) : (b))

 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))

 template<class T>

 inline void swap(T &a, T &b)

 {

     T tmp = a;a = b;b = tmp;

 }

 inline void read(long long &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '') c = ch, ch = getchar();

     while(ch <= '' && ch >= '') x = x *  + ch - '', ch = getchar();

     if(c == '-') x = -x;

 }

 const long long INF = 0x3f3f3f3f;

 const long long MAXN = ;

 const long long MOD = ;

 long long f[MOD + ], t, n, m;

 long long pow(long long a, long long b)

 {

     long long r = , base = a % MOD;

     for(;b;b >>= )

     {

         if(b & ) r *= base, r %= MOD;

         base *= base, base %= MOD;

     }

     return r;

 }

 long long ni(long long x)

 {

     return pow(x, MOD - );

 }

 long long C(long long n, long long m)

 {

     if(n < m) return ;

     int tmp = f[n] * ni(f[m]) % MOD , tmp2 = tmp * ni(f[n - m]) % MOD;

     return tmp2;

 }

 long long lucas(long long n, long long m)

 {

     if(!m) return ;

     else return C(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;

 }

 int main()

 {

     read(t);f[] = ;

     for(long long i = ;i <= MOD;++ i)

         f[i] = f[i - ] * i % MOD;

     for(long long i = ;i <= t;++ i)

     {

         read(n), read(m);

         printf("%lld\n", lucas(n, m));

     }

     return ;

 }

BZOJ2982