結果

問題 No.117 組み合わせの数
ユーザー ふーらくたるふーらくたる
提出日時 2016-07-10 22:17:30
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,506 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 24,832 KB
実行使用メモリ 8,224 KB
最終ジャッジ日時 2024-10-13 10:30:15
合計ジャッジ時間 12,711 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
using namespace std;

typedef long long ll;

ll ModFactorial(ll n, ll mod) {
    ll res = 1;
    for (int i = 1; i <= n; i++) {
        res = (res * i) % mod;
    }
    return res;
}

ll ModPow(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    else if (b % 2 == 0) {
        ll d = ModPow(a, b / 2, mod);
        return (d * d) % mod;
    } else {
        return (a * ModPow(a, b - 1, mod)) % mod;
    }
}

ll InverseElement(ll n, ll mod) {
    return ModPow(n, mod - 2, mod);
}

ll ModPermutation(ll n, ll r, ll mod) {
    if (n < r) return 0;
    return (ModFactorial(n, mod) * InverseElement(ModFactorial(n - r, mod), mod)) % mod;
}

ll ModCombination(ll n, ll r, ll mod) {
    if (n < r) return 0;
    return (ModPermutation(n, r, mod) * InverseElement(ModFactorial(r, mod), mod)) % mod;
}

ll ModHomogeneousProduct(ll n, ll r, ll mod) {
    return ModCombination(n + r - 1, r, mod);
}

const ll kMOD = 1000 * 1000 * 1000 + 7;
const int kMAX_T = 100010;

int T;

char query[100];

void Solve() {
    char c;
    int n, k;
    char buf[100];
    sscanf(query, "%c(%d,%d%s", &c, &n, &k, buf);

    if (query[0] == 'C') {
        printf("%lld\n", ModCombination(n, k, kMOD));
    } else if (query[0] == 'P') {
        printf("%lld\n", ModPermutation(n, k, kMOD));
    } else {
        printf("%lld\n", ModHomogeneousProduct(n, k, kMOD));
    }
}

int main() {
    scanf("%d", &T);

    for (int i = 0; i < T; i++) {
        scanf("%s", query);

        Solve();
    }

    return 0;
}
0