BZOJ2982: combination Lucas

时间:2022-01-01 22:14:33

Description

LMZn个不同的基友,他每天晚上要选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

Solution

Lucas板子

#include <bits/stdc++.h>

using namespace std ;

const int mod =  ;

int t , n , m ;
int fac[ mod + ] , ifac[ mod + ] ; int power( int a , int b ) {
int ans = , base = a ;
while( b ) {
if( b & ) ans = ans * base % mod ;
base = base * base % mod ;
b >>= ;
}
return ans ;
} int lucas( int a , int b ) {
if( a > b ) return ;
if( b <= mod ) return fac[ b ] % mod * ifac[ a ] % mod * ifac[ b - a ] % mod ;
return lucas( a % mod , b % mod ) % mod * lucas( a / mod , b / mod ) % mod ;
} int main() {
scanf( "%d" , &t ) ;
fac[ ] = ;
for( int i = ; i <= mod ; i ++ ) fac[ i ] = fac[ i - ] * i % mod ;
for( int i = ; i <= mod ; i ++ ) ifac[ i ] = power( fac[ i ] , mod - ) % mod ;
while( t -- ) {
scanf( "%d%d" , &n , &m ) ;
printf( "%d\n" , lucas( m , n ) ) ;
}
return ;
}