結果

問題 No.117 組み合わせの数
ユーザー kusaf_kusaf_
提出日時 2023-12-03 18:28:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 71 ms / 5,000 ms
コード長 2,029 bytes
コンパイル時間 2,499 ms
コンパイル使用メモリ 209,128 KB
実行使用メモリ 26,752 KB
最終ジャッジ日時 2023-12-03 18:28:47
合計ジャッジ時間 3,349 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;

struct Combinatorics {
  ll N;
  vector<mint> fac, finv, inv;
  Combinatorics() {}
  Combinatorics(ll COMAX): N(COMAX) {
    fac.resize(N + 1);
    finv.resize(N + 1);
    inv.resize(N + 1);
    fac[0] = finv[0] = inv[0] = 1;
    for(ll i = 0; i < N; i++) { fac[i + 1] = fac[i] * (i + 1); }
    finv[N] = fac[N].inv();
    for(ll i = N - 1; i >= 1; i--) { finv[i] = finv[i + 1] * (i + 1); }
    for(ll i = 0; i < N; i++) { inv[i + 1] = finv[i + 1] * fac[i]; }
  }
  inline mint operator()(ll n) {
    assert(-N <= n && n <= N);
    return n >= 0 ? fac[n] : finv[-n];
  }
  inline mint operator[](ll n) {
    assert(0 <= n && n <= N);
    return inv[n];
  }
  mint C(ll n, ll k) {
    if(n < 0 || k < 0 || n < k) { return 0; }
    if(n <= N) { return fac[n] * finv[n - k] * finv[k]; }
    else {  // naive, O(k)
      k = min(k, n - k);
      assert(k <= N);
      mint r = 1;
      for(ll i = 0; i < k; i++) { r *= n - i; }
      return r * finv[k];
    }
  }
  inline mint operator()(ll n, ll k) { return C(n, k); }
  mint P(ll n, ll k) {
    if(n < 0 || k < 0 || n < k) { return 0; }
    if(n <= N) { return fac[n] * finv[n - k]; }
    else {  // naive, O(k)
      k = min(k, n - k);
      assert(k <= N);
      mint r = 1;
      for(ll i = 0; i < k; i++) { r *= n - i; }
      return r;
    }
  }
  mint H(ll n, ll k) {
    if(n < 0 || k < 0) { return 0; }
    if(n == 0 && k == 0) { return 1; }
    return C(n + k - 1, k);
  }
} C(2000010);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll q;
  cin >> q;

  while(q--) {
    string s;
    cin >> s;
    s.pop_back();
    int i = 2;
    while(isdigit(s[i])) { ++i; }
    int n = stoi(s.substr(2, i - 2));
    int k = stoi(s.substr(i + 1));
    if(s[0] == 'C') { cout << C(n, k).val() << "\n"; }
    else if(s[0] == 'P') { cout << C.P(n, k).val() << "\n"; }
    else { cout << C.H(n, k).val() << "\n"; }
  }
}
0