2982: combination

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 703  Solved: 416 [][][]

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

 

Lucas定理

$C_n^m=C_{n\% p}^{m\% p}*C_{n/p}^{m/p}\% p$

#include 
      
       const int mod = 10007;int ksm(int a, int b){    int s = 1;    while(b){        if(b & 1) s = s * a % mod;        b >>= 1;        a = a * a % mod;    }    return s;}int fac[mod + 10], inv[mod + 10];inline int C(int n, int m){    if(n < m) return 0;    return fac[n] * inv[m] % mod * inv[n - m] % mod;}int Lucas(int n, int m){    if(!m) return 1;    return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;}int main(){    fac[0] = 1;    for(int i = 1; i < mod; i++) fac[i] = fac[i - 1] * i % mod;    inv[mod - 1] = ksm(fac[mod - 1], mod - 2);    for(int i = mod - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;    int t, n, m;    scanf("%d", &t);    while(t--){        scanf("%d %d", &n, &m);        printf("%d\n", Lucas(n, m));    }    return 0;}