結果

問題 No.117 組み合わせの数
ユーザー kusaf_kusaf_
提出日時 2023-12-03 18:15:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,005 bytes
コンパイル時間 2,308 ms
コンパイル使用メモリ 207,732 KB
実行使用メモリ 26,496 KB
最終ジャッジ日時 2024-09-26 22:13:08
合計ジャッジ時間 3,500 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:69:66: warning: 'id2' may be used uninitialized [-Wmaybe-uninitialized]
   69 |     string s1 = s.substr(2, id1 - 2), s2 = s.substr(id1 + 1, id2 - id1 - 1);
      |                                                              ~~~~^~~~~
main.cpp:64:13: note: 'id2' was declared here
   64 |     ll id1, id2;
      |             ^~~
main.cpp:69:33: warning: 'id1' may be used uninitialized [-Wmaybe-uninitialized]
   69 |     string s1 = s.substr(2, id1 - 2), s2 = s.substr(id1 + 1, id2 - id1 - 1);
      |                             ~~~~^~~
main.cpp:64:8: note: 'id1' was declared here
   64 |     ll id1, id2;
      |        ^~~

ソースコード

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;
    }
  }
} C(2e6);

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

  ll q;
  cin >> q;
  while(q--) {
    string s;
    cin >> s;
    ll id1, id2;
    for(ll i = 0; i < (ll)size(s); i++) {
      if(s[i] == ',') { id1 = i; }
      if(s[i] == ')') { id2 = i; }
    }
    string s1 = s.substr(2, id1 - 2), s2 = s.substr(id1 + 1, id2 - id1 - 1);
    ll n = stoi(s1), k = stoi(s2);
    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(n + k - 1, k).val() << "\n"; }
  }
}
0