結果

問題 No.117 組み合わせの数
ユーザー IL_mstaIL_msta
提出日時 2015-07-23 16:32:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 435 ms / 5,000 ms
コード長 1,621 bytes
コンパイル時間 978 ms
コンパイル使用メモリ 86,740 KB
実行使用メモリ 35,344 KB
最終ジャッジ日時 2023-09-22 21:41:44
合計ジャッジ時間 1,807 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
 
#include <algorithm>
#include <cmath>
 
#include <string>
//#include <array>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
 
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
const LL mod = 7+(int)1e9;
const int kmax = 1000001;
LL kai[2*kmax];
LL invkai[2*kmax];
LL ans[100000];

LL powmod(int n,int p){
	//a^p
	LL ans = 1;
	LL mel = n;
	while( p ){
		if( p%2 ){
			ans = (ans * mel)%mod;
		}
		p /= 2;
		mel = (mel * mel)%mod;
	}
	return ans;
}

LL ccc(int n,int k){
	LL ans;
	if( n < k){
		return 0;
	}
	ans = ( ( (kai[n]*invkai[n-k])%mod)*invkai[k] )%mod;
	//ans = (((kai[n]*powmod(kai[n-k],mod-2))%mod)*powmod(kai[k],mod-2))%mod;
	return ans;
}

void init(){
	kai[0] = 1;
	invkai[0] = 1;
	for(int i=1;i<2*kmax;++i){
		kai[i] = (i*kai[i-1])%mod;
		invkai[i] = powmod(kai[i],mod-2);
	}
}

LL ppp(int n,int k){
	return (ccc(n,k)*kai[k])%mod;
}

LL hhh(int n,int k){
	if(n==0 && k == 0){
		return 1;
	}
	return ccc(n+k-1,k);
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(16);//
	
	init();
	int T,N,K;
	cin>>T;
	char f,a;
	rep(i,T){
		cin>>f>>a>>N>>a>>K>>a;
		if(f=='C'){
			ans[i] = ccc(N,K);
		}else if( f=='P'){
			ans[i] = ppp(N,K);
		}else{
			ans[i] = hhh(N,K);
		}
	}
	rep(i,T){
		P(ans[i]);
	}
	
	return 0;
}
0