結果

問題 No.117 組み合わせの数
ユーザー mamekinmamekin
提出日時 2015-01-19 23:20:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 254 ms / 5,000 ms
コード長 1,945 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 92,816 KB
実行使用メモリ 18,648 KB
最終ジャッジ日時 2024-06-22 19:08:24
合計ジャッジ時間 1,429 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Mod
{
    static const int MOD = 1000000007;
    long long a;
public:
    Mod(){
        a = 0;
    }
    Mod(long long x){
        a = (x % MOD + MOD) % MOD;
    }
    const Mod operator+(const Mod& x) const{
        return Mod(a + x.a);
    }
    const Mod operator-(const Mod& x) const{
        return Mod(a - x.a);
    }
    const Mod operator*(const Mod& x) const{
        return Mod(a * x.a);
    }
    const Mod operator/(const Mod& x) const{ // フェルマーの小定理、MODが素数である場合のみ有効
        int b = MOD - 2;
        long long c = x.a;
        long long ret = 1;
        while(b > 0){
            if(b & 1){
                ret *= c;
                ret %= MOD;
            }
            c *= c;
            c %= MOD;
            b >>= 1;
        }
        return Mod(a * ret);
    }
    long long getValue(){
        return a;
    }
};

int main()
{
    vector<Mod> f(2000001, 1);
    for(int i=2; i<=2000000; ++i)
        f[i] = f[i-1] * i;

    int t;
    cin >> t;
    while(--t >= 0){
        char ope, c;
        int a, b;
        cin >> ope >> c >> a >> c >> b >> c;

        Mod ret = 0;
        if(ope == 'P'){
            if(a >= b)
                ret = f[a] / f[a-b];
        }
        else if(ope == 'C'){
            if(a >= b)
                ret = f[a] / f[b] / f[a-b];
        }
        else{
            if(a == 0 && b == 0)
                ret = 1;
            else if(a > 0)
                ret = f[a+b-1] / f[b] / f[a-1];
        }
        cout << ret.getValue() << endl;
    }

    return 0;
}
0