結果

問題 No.117 組み合わせの数
ユーザー zawakasuzawakasu
提出日時 2023-06-27 02:29:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 317 ms / 5,000 ms
コード長 2,596 bytes
コンパイル時間 4,272 ms
コンパイル使用メモリ 204,964 KB
実行使用メモリ 49,944 KB
最終ジャッジ日時 2024-07-03 21:10:16
合計ジャッジ時間 3,603 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 317 ms
49,944 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 ll add(ll a, ll b) {
        return norm(a + b);
    }

    inline ll inv(ll x) {
        return (x == 0 ? 0LL : mod - x);
    }

    inline ll sub(ll a, ll b) {
        return add(a, inv(b));
    }

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

    // CHECK!!! Hを使う時は、szを想定の2倍にしないと範囲外参照になる
    BinomMod(int sz) : N(sz + 1), F(sz + 1, 1),  invF(sz + 1, 1) {
        vector<ll> inv(sz + 1, 1);
        for (int i = 2 ; i < N ; i++) {
            F[i] = mul(F[i - 1], i);
            inv[i] = sub(mod, mul(inv[mod % i], (mod / i)));
            invF[i] = mul(invF[i - 1], inv[i]);
        }
    }

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

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

    // @brief: 重複組み合わせ nHr
    // @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