結果

問題 No.117 組み合わせの数
ユーザー まいん-まいん-
提出日時 2017-03-28 14:00:35
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 81 ms / 5,000 ms
コード長 2,641 bytes
コンパイル時間 476 ms
コンパイル使用メモリ 58,620 KB
実行使用メモリ 34,812 KB
最終ジャッジ日時 2024-07-06 13:21:00
合計ジャッジ時間 968 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
34,812 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:92:10: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |     fgets(buf, sizeof(buf), stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:98:14: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |         fgets(buf, sizeof(buf), stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <array>
#include <cstdlib>
#include <limits>
using namespace std;

using ll = long long;

const ll MOD = 1000000007;  // 10^9+7

// 参考: http://tubo28.me/algorithm/comb/
// ModCombination
namespace MC {
    const int MAX_N = 1000010;   // 10^6
    const ll MOD = 1000000007;  // 10^9+7
    // const ll MOD = numeric_limits<ll>::max();   // 剰余を取らない場合

    array<ll, 2 * MAX_N + 1> fact;
    array<ll, 2 * MAX_N + 1> inv_fact;  // n!の逆元

    void initialize(int);
    ll pow(ll, ll);
    ll factorial(ll);
    ll inverse(ll);
    ll inverse_factorial(ll);
    ll nPk(ll, ll);
    ll nCk(ll, ll);
    ll nHk(ll, ll);

    // 要素がn個あるとき
    void initialize(int n) {
        if (2 * n > 2 * MAX_N) {
            cerr << "現在のfactのサイズでは足りない可能性があります" << endl;
            exit(1);
        }

        // 階乗%MODを計算
        fact[0] = 1;
        for (ll i = 1; i <= 2 * MAX_N; i++) {
            fact[i] = (i * fact[i - 1]) % MOD;
        }
        // mod逆元の階乗を計算
        inv_fact[2 * MAX_N] = inverse(factorial(2 * MAX_N));
        for (ll i = 2 * MAX_N - 1; i >= 0; i--) {
            inv_fact[i] = ((i + 1) * inv_fact[i + 1]) % MOD;
        }
    }

    ll pow(ll a, ll b) {
        if (b == 0) return 1;
        else if (b % 2 == 0) {
            ll d = pow(a, b / 2);
            return (d * d) % MOD;
        } else {
            return (a * pow(a, b - 1)) % MOD;
        }
    }

    ll factorial(ll n) {
        return fact[n];
    }

    ll inverse(ll n) {
        return pow(n, MOD - 2);
    }

    ll inverse_factorial(ll n) {
        return inv_fact[n];
    }

    ll nPk(ll n, ll k) {
        if (n < 0 || n < k) return 0;
        else return (factorial(n) * inverse_factorial(n - k)) % MOD;
    }

    ll nCk(ll n, ll k) {
        if (n < 0 || n < k) return 0;
        else return (nPk(n, k) * inverse_factorial(k)) % MOD;
    }

    ll nHk(ll n, ll k) {
        if (n < 0 || k < 0) return 0;
        else if (k == 0) return 1;
        else return nCk(n + k - 1, k);
    }
};

int main() {
    int t;
    char buf[100];
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d", &t);

    MC::initialize(1000000);

    for (int i = 0; i < t; i++) {
        fgets(buf, sizeof(buf), stdin);

        char alpha;
        int n, k;
        sscanf(buf, "%c(%d,%d)", &alpha, &n, &k);

        ll val;
        if (alpha == 'C') val = MC::nCk(n, k);
        else if (alpha == 'P') val = MC::nPk(n, k);
        else val = MC::nHk(n, k);

        printf("%lld\n", val);
    }

    return 0;
}
0