結果

問題 No.117 組み合わせの数
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-08 21:26:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 300 ms / 5,000 ms
コード長 1,649 bytes
コンパイル時間 1,340 ms
コンパイル使用メモリ 144,844 KB
実行使用メモリ 19,068 KB
最終ジャッジ日時 2023-09-17 18:55:34
合計ジャッジ時間 2,327 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ(β)

テストケース

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

ソースコード

diff #

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define MAX 2000000


long long factorial[MAX + 1];
long long mod = (long long)1e9 + 7;

long long powmod(long long a, int p){
	if (p == 0) return 1;
	if (p % 2 == 1){
		return a * powmod(a, p - 1) % mod;
	}
	long long c = powmod(a, p / 2);
	return c * c % mod;
}

long long calcC(int N, int K){
	if (K < 0 || K > N) return 0;
	if (N == 0){
		if (K == 0) return 1;
		else return 0;
	}
	long long mul = factorial[N];
	long long div = factorial[K] * factorial[N - K] % mod;
	div = powmod(div, mod - 2);
	long long ans = mul * div % mod;
	return ans;
}

long long calcP(int N, int K){
	if (K < 0 || K > N) return 0;
	if (N == 0){
		if (K == 0) return 1;
		else return 0;
	}
	long long mul = factorial[N];
	long long div = factorial[N - K];
	div = powmod(div, mod - 2);
	long long ans = mul * div % mod;
	return ans;
}

long long calcH(int N, int K){
	if (K < 0) return 0;
	if (N == 0){
		if (K == 0) return 1;
		else return 0;
	}
	if (K == 0) return 1;
	long long mul = factorial[N + K - 1];
	long long div = factorial[N - 1] * factorial[(N + K - 1) - (N - 1)] % mod;
	div = powmod(div, mod - 2);
	long long ans = mul * div % mod;
	return ans;
}

int main(){
	int T;
	cin >> T;
	factorial[0] = 1;
	for (int i = 0; i < MAX; i++)
	{
		factorial[i + 1] = factorial[i] * (i + 1);
		factorial[i + 1] %= mod;
	}

	for (int t = 0; t < T; t++)
	{
		char C;
		int N, K;
		scanf(" %c(%d,%d)", &C, &N, &K);
		long long ans = 0;
		if (C == 'C'){
			ans = calcC(N, K);
		}
		if (C == 'P'){
			ans = calcP(N, K);
		}
		if (C == 'H'){
			ans = calcH(N, K);
		}
		cout << ans << endl;
	}
}
0