結果

問題 No.117 組み合わせの数
ユーザー hotpepsihotpepsi
提出日時 2015-09-08 01:03:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 284 ms / 5,000 ms
コード長 1,516 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 60,936 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-07-19 04:55:40
合計ジャッジ時間 1,408 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdio>

using namespace std;
typedef long long LL;
const LL MOD = 1000000007;

LL extgcd(LL a, LL b, LL &x, LL &y) {
	LL d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1, y = 0;
	}
	return d;
}

LL modinv(LL a, LL m) {
	LL x, y;
	extgcd(a, m, x, y);
	return (m + x % m) % m;
}

LL modpow(LL x, LL n, LL mod)
{
	LL a = 1;
	for (; n > 0; n >>= 1) {
		if (n & 1) a = (a * x) % mod;
		x = (x * x) % mod;
	}
	return a;
}

int main(int argc, char *argv[])
{
	LL T;
	string s;
	{
		getline(cin, s);
		stringstream ss(s);
		ss >> T;
	}

	LL fact[2000001];
	fact[0] = 1;
	for (LL a = 1; a <= 2000000; ++a) {
		fact[a] = (fact[a - 1] * a) % MOD;
	}
	for (int t = 0; t < T; ++t) {
		char type;
		LL n, k;
		getline(cin, s);
		sscanf(s.c_str(), "%c(%lld,%lld)", &type, &n, &k);
		LL ans = 0, a, b, c;
		switch (type) {
		case 'C':
			if (k <= n) {
				a = fact[n];
				b = modinv(fact[k], MOD);
				c = modinv(fact[n - k], MOD);
				ans = (((a * b) % MOD) * c) % MOD;
			}
			break;
		case 'P':
			if (k <= n) {
				a = (fact[n] * fact[k]) % MOD;
				b = modinv(fact[k], MOD);
				c = modinv(fact[n - k], MOD);
				ans = (((a * b) % MOD) * c) % MOD;
			}
			break;
		case 'H':
			if (k == 0) {
				ans = 1;
			} else if (n > 0) {
				a = fact[n + k - 1];
				b = modinv(fact[k], MOD);
				c = modinv(fact[n - 1], MOD);
				ans = (((a * b) % MOD) * c) % MOD;
			}
			break;
		}
		cout << ans << endl;
	}
	return 0;
}
0