結果

問題 No.117 組み合わせの数
ユーザー s14ti028s14ti028
提出日時 2019-02-11 15:20:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,228 bytes
コンパイル時間 729 ms
コンパイル使用メモリ 71,344 KB
実行使用メモリ 18,948 KB
最終ジャッジ日時 2023-09-25 13:57:56
合計ジャッジ時間 2,246 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Enumeration{
private:
    static constexpr long long int MOD = 1000000007;
    
    vector<long long int> fact, rfact;

    long long int inverse(const long long int x){
        long long int res = 1;
        long long int k = this->MOD-2;
        long long int y = x;

        while(k){
            if(k & 1) res = (res*y) % this->MOD;
            y = (y*y) % this->MOD;
            k >>= 1;
        }

        return res;
    }
public:
    Enumeration(const long long int n):fact(n), rfact(n){
        this->fact[0] = 1;
        for(int i = 1; i < n; ++i) this->fact[i] = (this->fact[i-1]*i) % this->MOD;
        
        this->rfact[n-1] = this->inverse(this->fact[n-1]);
        for(int i = n-2; i >= 0; --i) this->rfact[i] = (this->rfact[i+1]*(i+1)) % this->MOD;
    }

    long long int combination(const long long int n, const long long int k){
        if(k < 0 || n < k) return 0;

        return (this->fact[n]*(this->rfact[n-k]*this->rfact[k]) % this->MOD) % this->MOD;
    }

    long long int permutation(const long long int n, const long long int k){
        if(k < 0 || n < k) return 0;

        return (this->fact[n]*this->rfact[n-k]) % this->MOD;
    }

    long long int homogenous_product(const long long int n, const long long int k){
        if(n == 0 && k == 0) return 1;

        return this->combination(n+k-1, k);
    }
};

int main(){
    Enumeration E(1000010);

    int T;
    cin >> T;

    string S;
    for(int i = 0; i < T; ++i){
        cin >> S;
        
        string n = "";
        int j = 2;
        for(; j < S.size(); ++j){
            if(S[j] == ','){
                ++j;
                break;
            }else{
                n += S[j];
            }
        }

        string k = S.substr(j,S.size()-j-1);

        switch(S[0]){
            case 'C':
                cout << E.combination(stoi(n), stoi(k)) << endl;
                break;
            
            case 'P':
                cout << E.permutation(stoi(n), stoi(k)) << endl;
                break;

            case 'H':
                cout << E.homogenous_product(stoi(n), stoi(k)) << endl;
                break;
        }
    }
}
0