問題はこちら
No.117 組み合わせの数 - yukicoder
素直に階乗で計算するだけ
C(N,K)はによる単純なループによりO(K)で計算できるけど、KTが大きいのでこれではTLEになる
なので、事前に階乗を計算しておけば、各クエリは定数時間で答えられる
P:=10^9+7は素数なので、K<PにおいてK!はPを因数に持たず、互いに素であることから、mod PにおけるK!の逆元は存在する。
逆元はフェルマーの小定理により求める
横着をして、階乗の逆元を毎回求めているのでちょっと遅い
//繰り返し二乗法 long p(long a,int i){return i?p(a*a%P,i/2)*(i%2?a:1)%P:1;} int main(){ long frac[2000010]; int P=1e9+7,n,k,i; char c; frac[0]=1; for(i=1;i<=2000000;i++)frac[i]=frac[i-1]*i%P; //H(1000000,1000000)のとき2000000!まで必要(1敗) scanf("%d",&i); for(;--i;){ scanf(" %c(%d,%d)",&c,&n,&k) if(c=='H')n=n+k>0?n+k-1:0; //定義式通りだとH(0,0)のときC(-1,0)になって困るのでちょっと変えた if(n<k)puts("0"); else printf("%d\n",frac[n]*p(frac[n-k]*(c=='P'?1:frac[k])%P,P-2)%P); } return 0; }
'C','H','P'がそれぞれ67,72,80なのを利用して識別を工夫
powの引数もいい感じに睨んでやると省略できる事がわかる
long f[1<<21]; P=1e9+7,x,c,k; p(a,i){return i?1L*p(1L*a*a%P,i/2)*(i%2?a:1)%P:1;} main(n){ for(gets(f),*f=1;k++<2e6;f[k]=f[k-1]*k%P); for(;x=~scanf(" %c(%d,%d)",&c,&n,&k);printf("%d\n",n<k?0:f[n]*p(f[n-k]*(c%5?f[k]:1)%P,P-2)%P))c&8&&(n+=k)&&n--; }
240B
2017/03/02追記
pow関数のreturnを省略したい。xが手隙なのでそこへ代入してみる。xをlongにしておくといろいろ省略できる
//関数部分 p(a,i){return i?1L*p(1L*a*a%P,i/2)*(i%2?a:1)%P:1;} p(a,i){x=i?p(1L*a*a%P,i/2),x*(i%2?a:1)%P:1;} p(a,i){x=i?p(1L*a*a%P,i/2),i%2?x*a%P:x:1;} //printf部分 n<k?0:f[n]*p(f[n-k]*(c%5?f[k]:1)%P,P-2)%P n<k?0:(p(f[n-k]*(c%5?f[k]:1)%P,P-2),f[n]*x%P) n>=k?p(f[n-k]*(c%5?f[k]:1)%P,P-2),f[n]*x%P:0
ということで-8B+3Bで計5Bの短縮
long f[1<<21],k; P=1e9+7,x,c; p(a,i){k=i?p(1L*a*a%P,i/2),i%2?k*a%P:k:1;} main(n){ for(gets(f),*f=1;k++<2e6;f[k]=f[k-1]*k%P); for(;x=~scanf(" %c(%d,%ld)",&c,&n,&k);printf("%d\n",n>=k?p(f[n-k]*(c%5?f[k]:1)%P,P-2),k*f[n]%P:0))c&8&&(n+=k)&&n--; }
235B