結果

問題 No.117 組み合わせの数
ユーザー nakonisu
提出日時 2023-03-19 08:51:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 710 ms / 5,000 ms
コード長 2,278 bytes
コンパイル時間 1,387 ms
コンパイル使用メモリ 171,716 KB
実行使用メモリ 237,800 KB
最終ジャッジ日時 2024-09-18 13:41:45
合計ジャッジ時間 3,101 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << ">> " << #x << " : " << x << endl;
// templateEND

// 二項係数nCrの計算
// けんちょんさんのを拝借
// https://drken1215.hatenablog.com/entry/2018/06/08/210000
// maxを決めた前処理が必要
// 階乗のMODも計算できる（副産物?）
// **MOD確認** (MODは素数！)

// nCrを計算するための前処理、maxまでの階乗modをメモ化

// fac->階乗,finv->階乗の逆元,inv->単に逆数？
vector<long long> fac, finv, inv;
const long long MOD = 1000000007;
// テーブルを作る前処理
void COMinit(ll max) {
    fac.resize(max);
    finv.resize(max);
    inv.resize(max);
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < max; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数の計算
// **COMinitも必要**
// nCr(n,r)で二項係数を計算
long long nCr(long long n, long long r) {
    if (n < r) {
        // cerr << "n < r please" << endl;
        return 0;
    }
    if (n < 0 || r < 0) {
        // cerr << "n>=0 & r>=0 please" << endl;
        return 0;
    }
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

// 順列の計算！！
// **COMinitも必要**
// nCr(n,r)で二項係数を計算
long long nPr(long long n, long long r) {
    if (n < r) {
        // cerr << "n < r please" << endl;
        return 0;
    }
    if (n < 0 || r < 0) {
        // cerr << "n>=0 & r>=0 please" << endl;
        return 0;
    }
    return fac[n] * finv[n - r] % MOD;
}

int main() {
    // 前処理
    COMinit(1e7);

    ll t;
    cin >> t;
    char Type;
    ll n, r;
    for (int i = 0; i < t; i++) {
        scanf(" %c(%lld,%lld)", &Type, &n, &r);
        if (Type == 'C') {
            cout << nCr(n, r) << endl;
        } else if (Type == 'P') {
            cout << nPr(n, r) << endl;
        } else if (Type == 'H') {
            if (n == 0 && r == 0)
                cout << 1 << endl;
            else
                cout << nCr(n + r - 1, r) << endl;
        } else {
            cerr << "Type not found" << endl;
        }
    }
    return 0;
}
0