結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

vector<int> a{
    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,
};
int F = 1e7;

Modint fac(int N) {
  Modint x = a[N / F];
  for (int i = N / F * F + 1; i <= N; i++) {
    x *= i;
  }
  return x;
}

int main() {
  FAST_IO

  int N, K;
  cin >> N >> K;

  if (K * 2 >= N) {
    K = N - K;
  }

  if (N >= 998244353) {
    if (N - K + 1 <= 998244353) {
      cout << 0 << endl;
    } else {
      Modint x = 1;
      for (int i = 0; i < K; i++) {
        x *= N - i;
        x /= i + 1;
      }
      cout << x.val() << endl;
    }
    return 0;
  }

  Modint ans = fac(N) * fac(N - K).inv() * fac(K).inv();
  cout << ans.val() << endl;
}
0