結果

問題 No.117 組み合わせの数
ユーザー koyoprokoyopro
提出日時 2015-10-03 13:28:18
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,557 bytes
コンパイル時間 1,821 ms
コンパイル使用メモリ 160,992 KB
実行使用メモリ 39,152 KB
最終ジャッジ日時 2024-07-19 19:11:31
合計ジャッジ時間 2,284 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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];
signed main()
{
    int mod = (int)1e9 + 7;
    // 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("\n%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') {
            if (n < k) a = 0;
            else a = fact[n] * inv[n-k] * inv[k] % mod;
        } else {
            if (n == 0 && k == 0) a = 1;
            else if (n < 1) a = 0;
            else (a = fact[n+k-1] * inv[n-1] * inv[k]) %= mod;
        }
        ans.push_back(a);
    }
    for (int a : ans) {
        cout << a << endl;
    }
    return 0;
}
0