結果

問題 No.117 組み合わせの数
ユーザー まいん-まいん-
提出日時 2017-03-28 13:58:57
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 87 ms / 5,000 ms
コード長 3,262 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 54,860 KB
実行使用メモリ 34,860 KB
最終ジャッジ日時 2023-09-20 18:27:08
合計ジャッジ時間 1,100 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

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

ソースコード

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);

    /*
    printf("[test] {fact} %lld {inv_fact} % lld {result} %lld\n",
            MC::factorial(2 * MC::MAX_N),
            MC::inverse_factorial(2 * MC::MAX_N),
            (MC::factorial(2 * MC::MAX_N) *
            MC::inverse_factorial(2 * MC::MAX_N)) % MOD);
    */

    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);

        // printf("%c(%d,%d)\n", 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);

        /*
        printf("factorial %d is %lld\n", n, MC::factorial(n));
        printf("fact * inv_fact %d is %lld\n", n,
                (MC::factorial(n) * MC::inverse_factorial(n)) % MOD);
        printf("%d * inv(%d) is %lld\n", n, n,
                (n * MC::inverse(n)) % MOD);
        */
    }

    return 0;
}
0