bzoj2982: combination

借（cao）鉴（xi）自popoqqq大爷的lucas定理的写法

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int mod=10007;

int inv[mod],fac[mod];

int get(int n,int m){

	if(n<m) return 0;

	if(n<mod&&m<mod) return fac[n]*inv[m]%mod*inv[n-m]%mod;

	return get(n/mod,m/mod)*get(n%mod,m%mod)%mod;

}

int main(){

	fac[0]=1;

	rep(i,1,mod-1) fac[i]=fac[i-1]*i%mod;

	inv[0]=1;inv[1]=1;

	rep(i,2,mod-1) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

	rep(i,1,mod-1) inv[i]=inv[i-1]*inv[i]%mod;

	int t=read();

	while(t--){

		int n=read(),m=read();

		printf("%d\n",get(n,m));

	}

	return 0;

}

　　

2982: combination

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

 

[Submit][Status][Discuss]