結果

問題 No.117 組み合わせの数
ユーザー ふーらくたるふーらくたる
提出日時 2016-07-10 22:44:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 216 ms / 5,000 ms
コード長 1,974 bytes
コンパイル時間 557 ms
コンパイル使用メモリ 55,004 KB
実行使用メモリ 19,200 KB
最終ジャッジ日時 2024-04-21 12:06:52
合計ジャッジ時間 1,659 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 216 ms
19,200 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:86:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
main.cpp:89:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |         scanf("%s", query);
      |         ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const ll kMOD = 1000 * 1000 * 1000 + 7;
const int kMAX_T = 100010;
const int kMAX_N = 1000010;

int T;

char query[100];

ll memo[kMAX_N * 2];

ll ModFactorial(ll n, ll mod) {
    if (memo[n] > 0) return memo[n];
    ll res = 1;
    while (n > 1) {
        res = (res * n) % mod;
        n--;
        if (memo[n] > 0) {
            res = (res * memo[n]) % mod;
            break;
        }
    }
    return memo[n] = res;
}

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

ll InverseElement(ll n, ll mod) {
    return ModPow(n, mod - 2, mod);
}

ll ModPermutation(ll n, ll r, ll mod) {
    if (n < r) return 0;
    return (ModFactorial(n, mod) * InverseElement(ModFactorial(n - r, mod), mod)) % mod;
}

ll ModCombination(ll n, ll r, ll mod) {
    if (n < r) return 0;
    r = min(r, n - r);
    return (ModPermutation(n, r, mod) * InverseElement(ModFactorial(r, mod), mod)) % mod;
}

ll ModHomogeneousProduct(ll n, ll r, ll mod) {
    if (n == 0 && r == 0) return 1;
    return ModCombination(n + r - 1, r, mod);
}


void Solve() {
    char c;
    int n, k;
    char buf[100];
    sscanf(query, "%c(%d,%d%s", &c, &n, &k, buf);

    if (query[0] == 'C') {
        printf("%lld\n", ModCombination(n, k, kMOD));
    } else if (query[0] == 'P') {
        printf("%lld\n", ModPermutation(n, k, kMOD));
    } else {
        printf("%lld\n", ModHomogeneousProduct(n, k, kMOD));
    }
}

int main() {
    // 先に階乗を計算しておく
    ll res = 1;
    for (int i = 0; i < kMAX_N * 2; i++) {
        if (i > 1) {
            res = (res * i) % kMOD;
        }
        memo[i] = res;
    }

    scanf("%d", &T);

    for (int i = 0; i < T; i++) {
        scanf("%s", query);

        Solve();
    }

    return 0;
}
0