kmjp's blog

競技プログラミング参加記です

yukicoder : No.117 組み合わせの数

ライブラリのバグを修正できました。
http://yukicoder.me/problems/184

問題

T個のクエリが与えられる。
各クエリは計算種別(C,P,Hのいずれか)と2値N,Kからなる。
それぞれの種別に対し

  • 種別がC:  {}_N C_Kを答えよ
  • 種別がP:  {}_N P_Kを答えよ
  • 種別がH:  {}_N H_Kを答えよ

なお、N,Kは0以上10^6以下である。

解法

CとPの計算方法を考えると、 {}_N C_K = \frac{N!}{K!(N-K)!}, {}_N P_K = \frac{N!}{(N-K)!}なので階乗や階乗の逆数を事前に10^6まで求めておくと、各クエリはO(1)で処理できる。

Hについては基本的に {}_N H_K = {}_{N+K-1} C_Kである。
参考:組合せ (数学) - Wikipedia

しかしN==K==0の時だけはこの式では {}_0 H_0 = {}_{-1} C_0となりCombinationのルーチン次第ではうまく計算できない。
この場合だけ特別に処理してやる必要がある。
自分もこれでWAを連発した。

ll mo=1000000007;
const int NUM_=2000003;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

void init() {
	int i;
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
}
ll combi(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll perm(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return fact[N_]*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) {
	if(P_==0 && Q_==0) return 1;
	return combi(P_+Q_-1,Q_);
}

int T;
char hoge[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	init();
	scanf("%d",&T);
	FOR(i,T) {
		scanf("%1s(%d,%d)",hoge,&x,&y);
		ll ret=0;
		if(hoge[0]=='C') ret=combi(x,y);
		else if(hoge[0]=='P') ret=per(x,y);
		else if(hoge[0]=='H') ret=hcomb(x,y);
		cout<<ret<<endl;
	}
}

まとめ

ライブラリのバグ修正ゲーになってしまった。