BZOJ2982 combination

1431 ワード

私はこの問題にツッコミを入れないで、確かにあまり調和がとれていません.
直接組合せ数を求めるのは大体nlognレベルの工事であり、ここでは明らかに受け入れられない.
そこでlucasの定理を用いて
この定理の内容は大体次のように記述できる.
C(A,B)とAとBがP進数に分解した各対応桁の組合せ数の積がPに対して同余、
私も厳密に証明することはできませんが、、大体自分で考えてもいいです.
 
Code:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int p=10007;
int a[11],b[11];
int n,m,t,ans;

int pow(int x,int k){
	if 	(k==0)   return 0;
	if  (k==1)   return x;
	int now=pow(x,k/2);
	now=(now*now)%p;
	if  (k&1)   now=now*x%p;
	return now;
}

int c(int aa,int bb){
	if	(bb==0)  return 1;
	if  (aa<bb) return 0;
	int cur=1;
	for (int i=aa;i>aa-bb;i--)
	    cur=cur*i%p;
	for (int i=1;i<=bb;i++)
	    cur=cur*pow(i,p-2)%p;
	return cur;
}

int main(){
	scanf("%d",&t);
	while   (t--){
		scanf("%d%d",&m,&n);
		int len1=0,len2=0,ans=1;
		while   (m){
			a[len1++]=m%p;
			m/=p;
		}
		while   (n){
			b[len2++]=n%p;
			n/=p;
		}
		for (int i=0;i<max(len1,len2);i++)
		    ans=(ans*c(a[i],b[i]))%p;
		printf("%d
",ans); } //while(1); return 0; }