結果

問題 No.117 組み合わせの数
ユーザー s14ti028s14ti028
提出日時 2019-02-11 15:41:41
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 246 ms / 5,000 ms
コード長 1,939 bytes
コンパイル時間 1,841 ms
コンパイル使用メモリ 70,168 KB
実行使用メモリ 34,056 KB
最終ジャッジ日時 2023-09-25 14:33:25
合計ジャッジ時間 1,502 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

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

ソースコード

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(2000001);

    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);

        if(cmd == 'C'){
            cout << E.combination(N, K) << endl;
        }else if(cmd == 'P'){
            cout << E.permutation(N, K) << endl;
        }else if(cmd == 'H'){
            cout << E.homogenous_product(N, K) << endl;
        }
    }
}
0