結果

問題 No.117 組み合わせの数
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-08 21:26:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 289 ms / 5,000 ms
コード長 1,649 bytes
コンパイル時間 1,765 ms
コンパイル使用メモリ 159,344 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-07-04 13:19:36
合計ジャッジ時間 2,946 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 289 ms
19,072 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:73:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |                 scanf(" %c(%d,%d)", &C, &N, &K);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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