結果

問題 No.117 組み合わせの数
ユーザー y61mpnly61mpnl
提出日時 2021-06-13 17:12:19
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 153 ms / 5,000 ms
コード長 968 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 50,196 KB
実行使用メモリ 49,352 KB
最終ジャッジ日時 2023-08-24 20:10:47
合計ジャッジ時間 1,212 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 153 ms
49,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdint>
#include<vector>

const int MOD = 1e9 + 7;

template<typename Int>
struct Combination {
	std::vector<Int> fac, inv, finv;
	Combination(int n=1e6): fac(n), inv(n), finv(n) {
		fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
		for(Int i=2; i<n; i++){
			fac[i] = fac[i-1] * i % MOD;
			inv[i] = (-MOD/i + MOD) * inv[MOD%i] % MOD;
			finv[i] = finv[i-1] * inv[i] % MOD;
		}
	}

	Int C(Int n, Int k){
		if(n==k || k==0) return 1;
		if(n<0 || k<0 || n<k) return 0;
		return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
	}

	Int P(Int n, Int k){
		return C(n, k) * fac[k] % MOD;
	}

	Int H(Int n, Int k){
		return C(n+k-1, k);
	}
};


int main(){
	int t;
	scanf("%d", &t);

	Combination<int64_t> com(2e6);

	while(t--){
		getchar();
		char c = getchar();
		int n, k;
		scanf("(%d,%d)", &n, &k);
		if(c=='C') printf("%ld\n", com.C(n, k));
		if(c=='P') printf("%ld\n", com.P(n, k));
		if(c=='H') printf("%ld\n", com.H(n, k));
	}
	return 0;
}
0