結果

問題 No.117 組み合わせの数
ユーザー cutmdocutmdo
提出日時 2022-09-14 02:34:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 277 ms / 5,000 ms
コード長 2,881 bytes
コンパイル時間 828 ms
コンパイル使用メモリ 76,856 KB
実行使用メモリ 96,836 KB
最終ジャッジ日時 2023-08-21 02:50:07
合計ジャッジ時間 1,813 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/117"

#include <iostream>
#include <string>

#include <vector>

constexpr long long _ModCalculator_MOD = 1e9 + 7;
class ModCalculator {
    const long long m_mod;
    const std::vector<long long> m_fac;
    const std::vector<long long> m_finv;

    auto constructFac(long long s) {
        std::vector<long long> fac(s);
        fac[0] = fac[1] = 1;
        for(long long i = 2; i < s; ++i) {
            fac[i] = fac[i - 1] * i;
            if(fac[i] > m_mod) { fac[i] %= m_mod; }
        }
        return fac;
    }
    auto constructInv(long long s) {
        std::vector<long long> finv(s);
        finv[s - 1] = this->pow(m_fac[s - 1], m_mod - 2);
        for(long long i = s - 2; i >= 0; --i) {
            finv[i] = finv[i + 1] * (i + 1);
            if(finv[i] > m_mod) { finv[i] %= m_mod; }
        }
        return finv;
    }
public:
    ModCalculator(long long mod = _ModCalculator_MOD, long long size = 3 * 1e6) :
        m_mod(mod), m_fac(constructFac(size)), m_finv(constructInv(size)) {
    }

    long long pow(long long a, long long b) const {
        a %= m_mod;
        long long ans = 1;
        while(b > 0) {
            if(b & 1) { ans *= a; if(ans >= m_mod) { ans %= m_mod; } }
            b >>= 1; a *= a; if(a >= m_mod) { a %= m_mod; }
        }
        return ans;
    }

    auto fact(int n) const {
        if(n < 0) { return 0LL; }
        return m_fac[n];
    }

    auto factInv(int n) const {
        if(n < 0) { return 0LL; }
        return m_finv[n];
    }

    auto comb(int n, int r) const {
        auto val = fact(n) * factInv(r);
        if(val >= m_mod) { val %= m_mod; }
        val *= factInv(n - r);
        if(val >= m_mod) { val %= m_mod; }
        return val;
    }

    auto perm(int n, int r) const {
        auto val = fact(n) * factInv(n - r);
        if(val >= m_mod) { val %= m_mod; }
        return val;
    }

}calc;




using ll = long long;
using std::cout;
using std::cin;
constexpr char endl = '\n';
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

auto parse(const std::string s) {
    ll a = 0, b = 0;
    bool isa = true;
    for(unsigned int i = 2; i < s.size() - 1; ++i) {
        if(s[i] == ',') { isa = false; continue; }
        auto& x = ((isa) ? a : b);
        x = 10 * x + (s[i] - '0');
    }
    return std::pair<ll, ll>{a, b};
}

signed main() {
    ll t;
    cin >> t;

    constexpr ll MOD = 1e9 + 7;
    auto calc = ModCalculator(MOD);
    for(int _ = 0; _ < t; ++_) {
        std::string s;
        cin >> s;

        auto [n, k] = parse(s);
        if(s[0] == 'C') {
            cout << calc.comb(n, k) << endl;
        } else if(s[0] == 'P') {
            cout << calc.perm(n, k) << endl;
        } else {
            cout << calc.comb(std::max(0LL, n + k - 1), k) << endl;
        }
    }
}
0