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