yukicoder No.117 組み合わせの数

素直に階乗で計算するだけ
C(N,K)は $\prod_{i=1}^K \frac{N+1-i}{i}$ による単純なループによりO(K)で計算できるけど、KTが大きいのでこれではTLEになる

$\displaystyle{{}_NC_K=\frac{N!}{K!(N-K)!},\ \ {}_NP_K=\frac{N!}{(N-K)!},\ \ {}_NH_K={}_{N+K-1}C_K}$
なので、事前に階乗を計算しておけば、各クエリは定数時間で答えられる

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!まで必要（１敗）

	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

メモ

yukicoderでゆるふわgolf

yukicoder No.117 組み合わせの数