結果

問題 No.117 組み合わせの数
ユーザー zawakasuzawakasu
提出日時 2023-06-23 22:06:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 295 ms / 5,000 ms
コード長 2,587 bytes
コンパイル時間 2,179 ms
コンパイル使用メモリ 206,204 KB
実行使用メモリ 34,500 KB
最終ジャッジ日時 2024-07-01 01:50:37
合計ジャッジ時間 3,073 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <ll mod>
struct BinomMod {
    int N;
    vector<ll> F, invF;

    inline ll norm(ll x) {
        return ((x % mod) + mod) % mod;
    }

    inline ll mul(ll a, ll b) {
        return norm(a * b);
    }

    inline bool rangeCheck(int n) {
        return 0 <= n and n < N;
    }



    ll modinv(ll a) { // a^{mod - 2}フェルマーの小定理
        ll res = 1, base = a;
        ll p = mod - 2;
        while (p) {

            if (p & 1) res = mul(res, base);
            base = mul(base, base);
            p >>= 1;
        }
        return res;
    }

    BinomMod(int sz) : N(sz + 1), F(sz + 1, 1),  invF(sz + 1) {
        for (int i = 0 ; i < N ; i++) {
            F[i + 1] = mul(F[i], i + 1);
        } 
        
        invF[N] = modinv(F[N]); 

        for (int i = N ; i > 0 ; i--) {
            invF[i - 1] = mul(i, invF[i]);
        } 
    }

    // @brief 階乗 n!
    // nが負の場合、1 / n! を返す。
    ll Fac(int n) {
        assert(rangeCheck(abs(n)));
        return (n >= 0 ? F[n] : invF[-n]);
    }

    // @brief: 順列 nPr
    // @appendix: n個の区別可能なボールからr個選択して一列に並べる通り数
    ll P(int n, int r) {
        assert(rangeCheck(n) and rangeCheck(r));
        if (n < r) return 0;
        return mul(Fac(n), Fac(-(n - r)));
    }

    // @brief: 組み合わせ nCr
    // @appendix: n個の区別可能なボールからr個選択する通り数
    ll C(int n, int r) {
        assert(rangeCheck(n) and rangeCheck(r));
        if (n < r) return 0;
        return mul(P(n, r), Fac(-r));
    }

    // @brief: 組み合わせ
    // @appendix: r個の区別のできないボールをn個の部屋に分ける通り数(n - 1個の仕切りを敷く？)
    ll H(int n, int r) {
        if (n == 0 and r == 0) return 1;
        return C(n + r - 1, r);
    }
};

int read() {
    int res = 0;
    while (1) {
        char d; cin >> d;
        if ('0' <= d and d <= '9') {
            res = (res * 10 + (d - '0'));
        }
        else {
            break;
        }
    }
    return res;
}

int main() {
    int size = 2000000;
    BinomMod<1000000007> bm(size);
    
    int T; cin >> T;
    for (int _ = 0 ; _ < T ; _++) {
        char op; cin >> op;
        char c__; cin >> c__;
        int f = read(), b = read();
        if (op == 'P') cout << bm.P(f, b) << endl;
        else if (op == 'C') cout << bm.C(f, b) << endl;
        else if (op == 'H') cout << bm.H(f, b) << endl;
        else assert(!"input fail");
    }
}
0