結果

問題 No.117 組み合わせの数
ユーザー s14ti028s14ti028
提出日時 2019-02-11 15:30:50
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,036 bytes
コンパイル時間 606 ms
コンパイル使用メモリ 121,728 KB
実行使用メモリ 19,756 KB
最終ジャッジ日時 2024-05-07 18:31:18
合計ジャッジ時間 2,159 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
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;

        char cmd;
        int N, K;
        
        sscanf(S.c_str(), "%c(%d,%d)", &cmd, &N, &K);

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

            case 'H':
                cout << E.homogenous_product(N, K) << endl;
                break;
        }
    }
}
0