結果

問題 No.117 組み合わせの数
コンテスト
ユーザー data9824
提出日時 2015-06-28 20:47:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 412 ms / 5,000 ms
コード長 2,346 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 62,336 KB
実行使用メモリ 41,324 KB
最終ジャッジ日時 2024-07-07 20:49:32
合計ジャッジ時間 1,813 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

const long long MOD = 1000000007LL;
const long long MAX_FACTORIAL = 2000000LL;
long long factorial[MAX_FACTORIAL + 1];
long long inverse[MAX_FACTORIAL + 1];

long long combination(long long n, long long k) {
	if (n < k) {
		return 0;
	}
	long long result = factorial[n];
	result *= inverse[k];
	result %= MOD;
	result *= inverse[n - k];
	result %= MOD;
	return result;
}

long long permutation(long long n, long long k) {
	if (n < k) {
		return 0;
	}
	long long result = factorial[n];
	result *= inverse[n - k];
	result %= MOD;
	return result;
}

long long power(long long x, long long p) {
	long long result = 1;
	long long powered = x;
	for (; p != 0; p >>= 1) {
		if (p & 0x1) {
			result *= powered;
			result %= MOD;
		}
		powered *= powered;
		powered %= MOD;
	}
	return result;
}

int main() {
	factorial[0] = 1;
	long long x = 1;
	for (long long i = 1; i <= MAX_FACTORIAL; ++i) {
		x *= i;
		x %= MOD;
		factorial[i] = x;
	}
	/*
		整数aの、法pに関する合同類環における乗法逆元a^-1を求める。
		フェルマーの小定理より、aとpが互いに素なとき、
			a^(p-1) == 1 (mod p)
		変形すると、
			aa^(p-2) == 1 (mod p)
		となるので、a^-1=a^(p-2)である。
		n/a%pを求めるには、両辺にnをかけてaで割ると、
			na^(p-2) == n/a (mod p)
		となるので、n/a%p = na^(p-2)%pである。
		この問題では、p=10^9+7より、pは素数であり、
		aはpによる剰余なので a < p となり、aとpは互いに素である。
	*/
	for (long long i = 0; i <= MAX_FACTORIAL; ++i) {
		inverse[i] = power(factorial[i], MOD - 2);
	}
	int t;
	cin >> t;
	vector<string> s(t);
	for (int i = 0; i < t; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < t; ++i) {
		char type = s[i][0];
		size_t delimiter = s[i].find(',');
		long long n = atoll(s[i].substr(2, delimiter - 2).c_str());
		long long k = atoll(s[i].substr(delimiter + 1, s[i].size() - delimiter - 2).c_str());
		long long result;
		switch (type)
		{
		case 'C':
			result = combination(n, k);
			break;
		case 'P':
			result = permutation(n, k);
			break;
		case 'H':
			if (n == 0 && k == 0) {
				result = 1;
			} else {
				result = combination(n + k - 1, k);
			}
			break;
		}
		cout << result << endl;
	}
	return 0;
}
0