結果

問題 No.117 組み合わせの数
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-04-05 11:17:53
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 837 ms / 5,000 ms
コード長 1,821 bytes
コンパイル時間 1,721 ms
コンパイル使用メモリ 168,188 KB
実行使用メモリ 120,308 KB
最終ジャッジ日時 2023-08-30 22:54:42
合計ジャッジ時間 3,895 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 837 ms
120,308 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:49:15: 警告: ‘k’ may be used uninitialized [-Wmaybe-uninitialized]
   49 |         int n,k,tmp=0;
      |               ^
main.cpp:49:13: 警告: ‘n’ may be used uninitialized [-Wmaybe-uninitialized]
   49 |         int n,k,tmp=0;
      |             ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

struct Combination{
    const int MAX=5000010;
    const int MOD;
    vector<long long> FAC;
    vector<long long> INV;
    vector<long long> FAC_INV;
    Combination(const int MOD):
        MOD(MOD)
        {
            FAC=vector<long long>(MAX);
            INV=vector<long long>(MAX);
            FAC_INV=vector<long long>(MAX);
            FAC[0]=INV[1]=FAC_INV[0]=1;
            for(int i=1;i<MAX;i++){
                FAC[i]=FAC[i-1]*i%MOD;
                if(i>1) INV[i]=MOD-INV[MOD%i]*(MOD/i)%MOD;
                FAC_INV[i]=FAC_INV[i-1]*INV[i]%MOD;
            }
        }
    int C(int n,int r){
        if(n<0||r<0||n<r) return 0;
        return FAC[n]*FAC_INV[r]%MOD*FAC_INV[n-r]%MOD;
    }
    int P(int n,int r){
        if(n<0||r<0||n<r) return 0;
        return FAC[n]*FAC_INV[n-r]%MOD;
    }
    int H(int n,int r){
        if(r==0) return 1;
        return C(n+r-1,r);
    }
};

int main(){
    const int MOD=1e9+7;
    Combination com(MOD);
    int t; cin>>t;
    while(t--){
        string s; cin>>s;
        int n,k,tmp=0;
        for(int i=2;i<(int)s.size();i++){
            if(s[i]==')'){
                k=tmp;
            }else if(s[i]==','){
                n=tmp;
                tmp=0;
            }else{
                tmp*=10;
                tmp+=s[i]-'0';
            }
        }
        if(s[0]=='C') cout<<com.C(n,k)<<endl;
        if(s[0]=='P') cout<<com.P(n,k)<<endl;
        if(s[0]=='H') cout<<com.H(n,k)<<endl;
    }
    return 0;
}
0