結果

問題 No.117 組み合わせの数
ユーザー btkbtk
提出日時 2015-06-11 14:49:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 217 ms / 5,000 ms
コード長 2,204 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 65,040 KB
実行使用メモリ 34,400 KB
最終ジャッジ日時 2024-07-06 15:37:06
合計ジャッジ時間 1,393 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
namespace mod{
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
const int MOD=(int)(1e9+7);
	// aとbの最大公約数
	// O(log (a+b) )
	LL gcd(LL a,LL b){
		return (b==0)?a:gcd(b,a%b);
	}

	// aとbの最小公倍数
	// O(log (a+b) )
	LL lcm(LL a,LL b){
		return (a*b)/gcd(a,b);
	}

	// a x + b y = gcd(a, b)
	// O(log (a+b) )
	LL extgcd(LL a, LL b, LL &x, LL &y) {
	  LL g = a; x = 1; y = 0;
	  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
	  return g;
	}


	// iCjの組み合わせを全列挙してvectorに格納
	// (0<=j<=i<=n)
	// O(n^2)
	VVLL init_comb(int n){
		n++;
		VVLL res(n,VLL(n,0));
		for(int i=0;i<n;i++)res[i][0]=1;
		for(int i=1;i<n;i++)
			for(int j=1;j<=i;j++)
				res[i][j]=(res[i-1][j]+res[i-1][j-1])%MOD;
		return res;
	}

	// 1~nの逆元を求める(mod MOD)
	VLL list_mod_inverse(LL n){
	    VLL inv(n + 1);
	    inv[1] = 1;
	    for (int i = 2; i <= n; ++i)
	        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
	    return inv;
	}
	// 階乗
	// O(n)
	LL fact[2000001];
	// mを法とするaの逆元
	VLL invMod;

	void init(){
		fact[0]=1;
		invMod=list_mod_inverse(2000000);
		invMod[0]=1;
		for(int i=1;i<2000001;i++){
			fact[i]=(fact[i-1]*i)%MOD;
			invMod[i]=(invMod[i]*invMod[i-1])%MOD;
		}
	}

	// 組み合わせnCk (mod MOD)
	// O(n)
	LL Comb(LL n,LL k){
		LL u=fact[n];
		LL d=(invMod[k]*invMod[n-k])%MOD;
		return (u*d)%MOD;
	}

	LL Parm(LL n,LL k){
		LL u=fact[n];
		LL d=(invMod[n-k])%MOD;
		return (u*d)%MOD;
	}


}


int main(){
mod::init();
	int T;
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		char c=s[0];
		int i=2;
		mod::LL n=0;
		for(;s[i]!=',';i++){
			n*=10;
			n+=(s[i]-'0');
		}
		i++;
		int k=0;
		for(;s[i]!=')';i++){
			k*=10;
			k+=(s[i]-'0');
		}
		if(n==0&&k==0){
			cout<<1<<endl;
			continue;
		}
		else if(n==0){
			cout<<0<<endl;
			continue;
		}
		switch(c){
		case 'P':
			if(k>n)cout<<0<<endl;
			else
			cout<<mod::Parm(n,k)<<endl;
			break;
		case 'H':
			n=n+k-1;
			cout<<mod::Comb(n,k)<<endl;
			break;
		default:
			if(k>n)cout<<0<<endl;
			else
			cout<<mod::Comb(n,k)<<endl;
			break;
		}

	}
	return 0;
}
0