結果

問題 No.117 組み合わせの数
ユーザー koyoprokoyopro
提出日時 2015-10-03 13:39:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 262 ms / 5,000 ms
コード長 1,645 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 148,028 KB
実行使用メモリ 38,744 KB
最終ジャッジ日時 2023-09-27 01:33:42
合計ジャッジ時間 2,161 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(int i=0; i<(n); i++)
#define MAX 2222222
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define int long long

int T;
int fact[MAX];
int inv[MAX];
int mod = (int)1e9 + 7;
int comb(int n, int k) {
    if (k < 0 || n < k) return 0;
    return (fact[n] * inv[n-k] % mod) * inv[k];
}
int hcomb(int n, int k) {
    if (n == 0 && k == 0) return 1;
    return comb(n+k-1, k);
}
signed main()
{
    // n!をO(N)で求める
    fact[0] = fact[1] = 1;
    FOR(i,2,MAX) (fact[i] = i * fact[i-1]) %= mod;
    // n!の逆元をO(logP+N)で求める
    int k = 0;
    int ret = 1;
    int tmp = fact[MAX-1];;
    int e = mod - 2;
    while(1 << k <= e) {
        if (e & (1 << k)) {
            ret *= tmp;
            ret %= mod;
        }
        tmp *= tmp; // 2乗していく
        tmp %= mod;
        k++;
    }
    inv[MAX-1] = ret; // (MAX-1)!の逆元が求まった
    // O(N)で順番に逆元を埋めていく
    inv[0] = inv[1] = 1;
    RFOR(i,2,MAX-1) {
        inv[i] = inv[i+1] * (i+1) % mod;
    }
    cin >> T;
    char c;
    int n;
    vector<int> ans;
    REP(i,T) {
        scanf(" %c(%lld,%lld)", &c, &n, &k);
        int a = 0;
        if (c == 'P') {
            if (n < k) a = 0;
            else a = fact[n] * inv[n-k] % mod;
        } else if (c == 'C') {
            a = comb(n, k) % mod;
        } else {
            if (n == 0 && k == 0) a = 1;
            else a = comb(n+k-1, k) % mod;
        }
        ans.push_back(a);
    }
    for (int a : ans) {
        cout << a << endl;
    }
    return 0;
}
0