結果

問題 No.117 組み合わせの数
ユーザー goodbatongoodbaton
提出日時 2015-06-25 02:56:16
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,623 bytes
コンパイル時間 594 ms
コンパイル使用メモリ 71,744 KB
実行使用メモリ 14,428 KB
最終ジャッジ日時 2023-09-22 00:36:29
合計ジャッジ時間 13,147 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef long long ll;

ll fac_memo[2000000] = {0};

ll factorial(int n,int M){
    ll ret = 1;
    if(n<=1) return 1;
    if(fac_memo[n]) return fac_memo[n];
    
    for(int i=1;i<=n;i++){
        ret = (ret*i)%M;
    }
    
    return fac_memo[n] = ret;
}

ll power(int k,int n,int M){
    if(n==0) return 1;
    if(n==1) return (ll)k;
    
    ll ret = power(k,n/2,M);
    
    ret=(ret*ret)%M;
    
    if(n%2==1)
        ret=(ret*k)%M;
    
    return ret;
}

//nCm (mod p) p is prime number
int C(int n,int m,int M){
    
    if(m==0 || n==m) return 1;
    
    ll chi = factorial(n,M);
    ll mot = (factorial(m,M) * factorial(n-m,M))%M;
    
    
    mot = power((int)mot,M-2,M);
    
    ll ret = (chi*mot)%M;
    
    return (int)ret;
}

int P(int n,int m,int M){
    
    if(m==0) return 1;
    
    ll chi = factorial(n,M);
    ll mot = factorial(n-m,M);
    
    
    mot = power((int)mot, M-2,M);
    
    ll ret = (chi*mot)%M;
    
    return (int)ret;
}

int H(int n,int m,int M){
    return C(n+m-1,m,M);
}

int main(){
    int t,n,k,ans;
    int mod = 1000000007;
    char S;
    
    scanf("%d",&t);
    
    for(int i=0;i<t;i++){
        scanf(" %c(%d,%d)",&S,&n,&k);
        
        if(S=='C'){
            ans = C(n,k,mod);
        }else if(S=='P'){
            ans = P(n,k,mod);
        }else{
            ans = H(n,k,mod);
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}
0