結果

問題 No.117 組み合わせの数
ユーザー bad_boy_gaogaobad_boy_gaogao
提出日時 2021-06-17 18:50:42
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,299 bytes
コンパイル時間 1,618 ms
コンパイル使用メモリ 169,056 KB
実行使用メモリ 50,068 KB
最終ジャッジ日時 2023-09-01 21:40:24
合計ジャッジ時間 2,751 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define BE(x) x.begin(), x.end()

const ll m = 1000000007;
const ll max_n = 2000000;

vector<ll> inv(max_n+1), fact(max_n+1), finv(max_n+1);
bool pre = true;

void comb_pre() {
    inv[1]  = 1;
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    for (ll i = 2; i <= max_n; i++) {
        inv[i]  = m - inv[m%i] * (m/i) % m; // inverse for i
        fact[i] = fact[i-1] * i % m;        // i!
        finv[i] = finv[i-1] * inv[i] % m;   // inverse for i!
    }
}

ll comb (ll n, ll k) {
    if (pre) {
        comb_pre();
        pre = false;
    }
    if (n<k || n<0 || k<0)
        return 0;
    else
        return fact[n] * (finv[k] * finv[n-k] % m) % m;
} // n and k up to about 10^7 // pre:O(max_n), query:O(1)

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string s;
        cin >> s;

        int nb = 2, ne = 3;
        while (s[ne] != ',') ne++;
        int kb = ne+1, ke = ne+2;
        while (s[ke] != ')') ke++;
        ll n = stoll(s.substr(nb, ne-nb));
        ll k = stoll(s.substr(kb, ke-kb));

        if (s[0] == 'C') cout << comb(n,k) << endl;
        if (s[0] == 'P') cout << comb(n,k) * fact[k] % m << endl;
        if (s[0] == 'H') cout << comb(n+k-1,k) << endl;
    }
}
0