結果

問題 No.117 組み合わせの数
ユーザー Lay_ecLay_ec
提出日時 2015-01-05 00:36:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 336 ms / 5,000 ms
コード長 1,559 bytes
コンパイル時間 677 ms
コンパイル使用メモリ 80,712 KB
実行使用メモリ 81,572 KB
最終ジャッジ日時 2024-06-13 02:34:04
合計ジャッジ時間 1,778 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
#include <queue>

using namespace std;
 
const double eps=1e-10;

const int dy[]={-1,-1,0,1,1, 1, 0,-1};
const int dx[]={ 0, 1,1,1,0,-1,-1,-1};

const long long mod=1000000000+7;

//a^b
long long mod_pow(long long a,long long b){
	long long res=1;

	while(b>0){
		if((b&1)==1) res=(res*a)%mod;
		b >>=1;
		a=(a*a)%mod;
	}
	return res;
}

//a/b
long long mod_div(long long a,long long b){
	return a*mod_pow(b,mod-2)%mod;
}

long long fact[10000001];

int main()
{

	fact[0]=fact[1]=1;
	for(long i=2;i<10000001;i++){
		fact[i]=(i*fact[i-1])%mod;
	}

	int t;
	cin>>t;


	for(int i=0;i<t;i++){
		char c;
		cin>>c;
		if(c=='C'){
			long long n,k;
			char dummy;
			cin>>dummy>>n>>dummy>>k>>dummy;

			if(n<k) cout<<0<<endl;
			else{
				
				long long a=mod_div(fact[n],fact[k]);
				long long b=mod_div(a,fact[n-k]);
				cout<<b<<endl;
			}
		}else if(c=='P'){
			long long n,k;
			char dummy;
			cin>>dummy>>n>>dummy>>k>>dummy;

			if(n<k) cout<<0<<endl;
			else{
				
				cout<<mod_div(fact[n],fact[n-k])<<endl;
			}

		}else{

			//H(n,k)=C(n+k-1,k)

			long long n,k;
			char dummy;
			cin>>dummy>>n>>dummy>>k>>dummy;

			if(n==0 && k==0) cout<<1<<endl;
			else if(n+k-1-k<0) cout<<0<<endl;
			else{
				
				long long a=mod_div(fact[n+k-1],fact[k]);
				long long b=mod_div(a,fact[n+k-1-k]);

				cout<<b<<endl;
			}

		}

	}

	return 0;
}
0