結果

問題 No.117 組み合わせの数
ユーザー Today
提出日時 2025-02-21 00:21:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 375 ms / 5,000 ms
コード長 3,991 bytes
コンパイル時間 873 ms
コンパイル使用メモリ 88,940 KB
実行使用メモリ 97,580 KB
最終ジャッジ日時 2025-02-21 00:21:43
合計ジャッジ時間 2,109 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:123:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  123 |     scanf("%d\n", &t);
      |     ~~~~~^~~~~~~~~~~~
main.cpp:129:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |         scanf("%c(%d,%d)\n", &c, &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template <int mod>
class Combination {
    static_assert(mod >= 2);

    static Combination *s_instance;
    int m_sz;
    std::vector<long long> m_fact;  // m_fact[n]:=(nの階乗).
    std::vector<long long> m_inv;   // m_inv[n]:=(nの逆元).
    std::vector<long long> m_finv;  // m_finv[n]:=(nの階乗の逆元).

    Combination() : m_sz(2), m_fact({1, 1}), m_inv({-1, 1}), m_finv({1, 1}) {}

    static Combination *instance() {
        if(!s_instance) s_instance = new Combination;
        return s_instance;
    }
    void calc(int sz) {
        assert(sz <= mod);
        if(sz <= m_sz) return;
        reserve_internal(sz);
        for(int n = m_sz; n < sz; ++n) {
            m_fact.push_back(m_fact[n - 1] * n % mod);
            m_inv.push_back(mod - m_inv[mod % n] * (mod / n) % mod);
            m_finv.push_back(m_finv[n - 1] * m_inv[n] % mod);
        }
        m_sz = sz;
    }
    long long fact(int n) {
        assert(n >= 0);
        calc(n + 1);
        return m_fact[n];
    }
    long long inv(int n) {
        assert(n >= 1);
        calc(n + 1);
        return m_inv[n];
    }
    long long finv(int n) {
        assert(n >= 0);
        calc(n + 1);
        return m_finv[n];
    }
    long long nPk_internal(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        calc(n + 1);
        return m_fact[n] * m_finv[n - k] % mod;
    }
    long long nCk_internal(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        calc(n + 1);
        return m_fact[n] * m_finv[n - k] % mod * m_finv[k] % mod;
    }
    void resize_internal(int sz) {
        assert(0 <= sz);
        if(sz < 2) return;
        if(m_sz < sz) {
            reserve_internal(sz);
            return;
        }
        m_fact.resize(sz);
        m_inv.resize(sz);
        m_finv.resize(sz);
        m_sz = sz;
    }
    void reserve_internal(int cap) {
        assert(0 <= cap);
        m_fact.reserve(cap);
        m_inv.reserve(cap);
        m_finv.reserve(cap);
    }
    void shrink_to_fit_internal() {
        m_fact.shrink_to_fit();
        m_inv.shrink_to_fit();
        m_finv.shrink_to_fit();
    }

public:
    static constexpr int modulus() { return mod; }
    // 階乗．O(1).
    static long long factorial(int n) { return instance()->fact(n); }
    // 逆元．O(1).
    static long long inverse(int n) { return instance()->inv(n); }
    // 階乗の逆元．O(1).
    static long long inverse_fact(int n) { return instance()->finv(n); }
    // 順列．O(1).
    static long long nPk(int n, int k) { return instance()->nPk_internal(n, k); }
    // 組合せ．O(1).
    static long long nCk(int n, int k) { return instance()->nCk_internal(n, k); }
    // 重複組合せ．O(1).
    static long long nHk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(k == 0) return 1;
        if(n == 0) return 0;
        return instance()->nCk_internal(k + n - 1, k);
    }
    static void resize(int sz) { instance()->resize_internal(sz); }
    static void reserve(int cap) { instance()->reserve_internal(cap); }
    static void shrink_to_fit() { instance()->shrink_to_fit_internal(); }
    static void destroy() {
        delete s_instance;
        s_instance = nullptr;
    }
};

template <int mod>
Combination<mod> *Combination<mod>::s_instance = nullptr;

using Combination998244353 = Combination<998'244'353>;
using Combination1000000007 = Combination<1'000'000'007>;

int main() {
    int t;
    scanf("%d\n", &t);

    Combination1000000007::reserve(1e6 + 1);
    while(t--) {
        char c;
        int n, k;
        scanf("%c(%d,%d)\n", &c, &n, &k);

        long long ans;
        if(c == 'C') ans = Combination1000000007::nCk(n, k);
        else if(c == 'P') ans = Combination1000000007::nPk(n, k);
        else ans = Combination1000000007::nHk(n, k);
        cout << ans << "\n";
    }
}
0