BZOJ2982: combination Lucas模板-白红宇

BZOJ2982: combination Lucas模板

阅读量：4589 次

发布时间：2019-06-09

本文共 2088 字，大约阅读时间需要 6 分钟。

2982: combination

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 734 Solved: 437

[][][]

Description

LMZ

有

个不同的基友，他每天晚上要选

个进行

[

河蟹

]

，而且要求每天晚上的选择都不一样。那么

LMZ

能够持续多少个这样的夜晚呢？当然，

LMZ

的一年有

10007

天，所以他想知道答案

mod 10007

的值。

(1<=m<=n<=200,000,000)

Input

第一行一个整数

，表示有

组数据。

(t<=200)

接下来

行每行两个整数

n, m

，如题意。

Output

行，每行一个数，为

C(n, m) mod 10007

的答案。

Sample Input

5 1

5 2

7 3

4 2

Sample Output

HINT

Source

lucas模板题

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                 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
                 
                  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\n", lucas(n, m));67 }68 return 0;69 }