結果

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

ソースコード

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[] = {1,295201906,160030060,957629942,545208507,213689172,760025067,939830261,506268060,39806322,808258749,440133909,686156489,741797144,390377694,12629586,544711799,104121967,495867250,421290700,117153405,57084755,202713771,675932866,79781699,956276337,652678397,35212756,655645460,468129309,761699708,533047427,287671032,206068022,50865043,144980423,111276893,259415897,444094191,593907889,573994984,892454686,566073550,128761001,888483202,251718753,548033568,428105027,742756734,546182474,62402409,102052166,826426395,159186619,926316039,176055335,51568171,414163604,604947226,681666415,511621808,924112080,265769800,955559118,763148293,472709375,19536133,860830935,290471030,851685235,242726978,169855231,612759169,599797734,961628039,953297493,62806842,37844313,909741023,689361523,887890124,380694152,669317759,367270918,806951470,843736533,377403437,945260111,786127243,80918046,875880304,364983542,623250998,598764068,804930040,24257676,214821357,791011898,954947696,183092975,0,};
  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