結果

問題 No.117 組み合わせの数
ユーザー HachimoriHachimori
提出日時 2015-01-05 00:06:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 246 ms / 5,000 ms
コード長 1,365 bytes
コンパイル時間 1,521 ms
コンパイル使用メモリ 52,896 KB
実行使用メモリ 11,236 KB
最終ジャッジ日時 2023-09-03 21:51:45
合計ジャッジ時間 1,960 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<cstdio>
using namespace std;
const int BUF = 2000005;
const int MOD = 1000000007;


int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

int modpow(int p, int n) {
    if (n == 0) return 1;
    int t = modpow(p, n / 2);
    return n & 1 ? mul(t, mul(t, p)) : mul(t, t);
}

int inv(int v) {
    return modpow(v, MOD - 2);
}


char ch;
int N, K;
int factorial[BUF];

void makeTable() {
    factorial[0] = 1;
    for (int i = 1; i < BUF; ++i)
        factorial[i] = mul(factorial[i - 1], i);
}


void read() {
    scanf(" %c(%d,%d)", &ch, &N, &K);
}


int nCk(int n, int k) {
    if (n < 0 || k < 0 || n - k < 0)
        return 0;
    return mul(factorial[n], mul(inv(factorial[n - k]), inv(factorial[k])));
}


int nPk(int n, int k) {
    if (n < 0 || k < 0 || n - k < 0)
        return 0;
    return mul(factorial[n], inv(factorial[n - k]));
}


int nHk(int n, int k) {
    if (n == 0 && k == 0) return 1;
    return nCk(n + k - 1, k);
}


void work() {
    switch(ch) {
    case 'C':
        cout << nCk(N, K) << endl;
        break;
    case 'P':
        cout << nPk(N, K) << endl;
        break;
    case 'H':
        cout << nHk(N, K) << endl;
        break;
    }
}


int main() {
    makeTable();

    int cases;
    cin >> cases;
    for (int i = 0; i < cases; ++i) {
        read();
        work();
    }
    
    return 0;
}
0