結果

問題 No.117 組み合わせの数
ユーザー Today
提出日時 2025-04-07 00:31:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,517 bytes
コンパイル時間 1,139 ms
コンパイル使用メモリ 86,428 KB
実行使用メモリ 50,260 KB
最終ジャッジ日時 2025-04-07 00:31:31
合計ジャッジ時間 1,956 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:75:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |     scanf("%d\n", &t);
      |     ~~~~~^~~~~~~~~~~~
main.cpp:81:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |         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);

    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_inv_fact;  // m_inv_fact[n]:=(nの階乗の逆元).

public:
    Combination() : Combination(2) {}
    explicit Combination(int n) : m_sz(n), m_fact(n), m_inv(n), m_inv_fact(n) {
        assert(n >= 2);
        m_fact[0] = m_fact[1] = 1;
        m_inv[1] = 1;
        m_inv_fact[0] = m_inv_fact[1] = 1;
        for(int i = 2; i < m_sz; ++i) {
            m_fact[i] = m_fact[i - 1] * i % mod;
            m_inv[i] = mod - m_inv[mod % i] * (mod / i) % mod;
            m_inv_fact[i] = m_inv_fact[i - 1] * m_inv[i] % mod;
        }
    }

    static constexpr int modulus() { return mod; }
    // 階乗．O(1).
    int size() const { return m_sz; }
    long long factorial(int n) const {
        assert(0 <= n and n < size());
        return m_fact[n];
    }
    // 逆元．O(1).
    long long inverse(int n) const {
        assert(1 <= n and n < size());
        return m_inv[n];
    }
    // 階乗の逆元．O(1).
    long long inverse_factorial(int n) const {
        assert(0 <= n and n < size());
        return m_inv_fact[n];
    }
    // 順列．O(1).
    long long nPk(int n, int k) const {
        assert(0 <= n and n < size());
        assert(k >= 0);
        if(n < k) return 0;
        return m_fact[n] * m_inv_fact[n - k] % mod;
    }
    // 組合せ．O(1).
    long long nCk(int n, int k) const {
        assert(0 <= n and n < size());
        assert(k >= 0);
        if(n < k) return 0;
        return m_fact[n] * m_inv_fact[n - k] % mod * m_inv_fact[k] % mod;
    }
    // 重複組合せ．O(1).
    long long nHk(int n, int k) const {
        assert(n >= 0);
        assert(k >= 0);
        if(k == 1) return 1;
        if(n == 0) return 0;
        return nCk(k + n - 1, k);
    }
};

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

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

    Combination1000000007 comb(2e6);
    while(t--) {
        char c;
        int n, k;
        scanf("%c(%d,%d)\n", &c, &n, &k);

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