結果

問題 No.3394 Big Binom
コンテスト
ユーザー テナガザル
提出日時 2025-12-01 00:24:28
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,038 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 949 ms
コンパイル使用メモリ 100,980 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-01 00:24:48
合計ジャッジ時間 2,811 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

long long pow(long long a, long long k, long long m)
{
  long long ret = 1;
  for (a %= m; k > 0; k >>= 1, a = a * a % m) if (k & 1) ret = ret * a % m;
  return ret;
}

int main()
{
  const int p[] = {35305197,245648024,310896195,728580680,694848220,330648209,902265665,191674863,372114502,421678599,331620780,763055415,522844932,246782240,17887055,756394555,847111886,536345187,108918658,421897391,687660791,360152987,957181936,572487995,91057667,259048065,625039406,347713633,567453693,201761277,88471230,743270971,427929963,801357509,545242190,444220190,809069539,43772996,653931167,975751463,843195842,104038365,829293351,621494557,449639156,268827826,380948022,700958286,418799947,779957103,399276049,33641544,729687358,140333252,618233873,4696413,327882638,140760728,172725728,811023346,309381680,695753612,316273420,890142251,963741496,724770477,253512500,252152121,172731458,77283583,291200798,193553412,277230214,925752181,594391396,203768372,1400659,522927509,321370340,230436398,909740184,954961390,565386092,616350076,384359928,641771338,369146440,687230644,781983120,202725520,404806075,288141849,494059012,875448307,661892471,143778807,602710200,98059376,125598866,777990065,};
  const int mod = 998244353, b = 10000000;
  int n, k;
  cin >> n >> k;
  if (n - k < k) k = n - k;
  long long ans = 1;
  if (k <= 3e6)
  {
    long long tmp = 1;
    for (int i = 1; i <= k; ++i)
    {
      tmp = tmp * i % mod;
      ans = ans * (n - i + 1) % mod;
    }
    tmp = pow(tmp, mod - 2, mod);
    ans = ans * tmp % mod;
  }
  else
  {
    auto cal = [&](int x) -> long long
    {
      int id = x / b;
      long long ret = p[id];
      for (long long i = id * b + 1; i <= x; ++i) ret = ret * i % mod;
      return ret;
    };
    int id = n / b;
    ans = cal(n);
    long long tmp = cal(n - k);
    ans = ans * pow(tmp, mod - 2, mod) % mod;
    tmp = cal(k);
    ans = ans * pow(tmp, mod - 2, mod) % mod;
  }
  cout << ans << endl;
}
0