結果

問題 No.117 組み合わせの数
ユーザー btkbtk
提出日時 2015-06-11 14:38:45
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 208 ms / 5,000 ms
コード長 2,242 bytes
コンパイル時間 631 ms
コンパイル使用メモリ 64,640 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-07-06 15:36:59
合計ジャッジ時間 1,157 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 208 ms
18,944 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);
// ab
// O(log (a+b) )
LL gcd(LL a,LL b){
return (b==0)?a:gcd(b,a%b);
}
// ab
// 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;
}
// ma
// O(log a)
LL invMod(LL a) {
LL x, y;
if (extgcd(a, MOD, x, y) == 1)
return (x + MOD) % MOD;
else
return 0; // unsolvable
}
// iCjvector
// (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;
}
//
// O(n)
LL fact[2000001];
void init(){
fact[0]=1;
for(int i=1;i<2000001;i++)
fact[i]=(fact[i-1]*i)%MOD;
}
// nCk (mod MOD)
// O(n)
LL Comb(LL n,LL k){
LL u=fact[n];
LL d=(fact[k]*fact[n-k])%MOD;
return (u*invMod(d))%MOD;
}
LL Parm(LL n,LL k){
LL u=fact[n];
LL d=(fact[n-k])%MOD;
return (u*invMod(d))%MOD;
}
// 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;
}
}
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0