結果

問題 No.3394 Big Binom
コンテスト
ユーザー miya145592
提出日時 2025-12-03 23:20:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 618 ms / 2,000 ms
コード長 1,916 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 394 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 60,180 KB
最終ジャッジ日時 2025-12-03 23:20:46
合計ジャッジ時間 7,001 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def nCr(n, k, mod):
    L = 10**7
    dp = [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]
    k = min(k, n-k)
    if n-k>=mod:
        bunsi = 1
        for i in range(n-k+1, n+1):
            bunsi = bunsi * i % mod
        bunbo = 1
        for i in range(1, k+1):
            bunbo = bunbo * i % mod
        ans = bunsi * pow(bunbo, mod-2, mod) % mod
        return ans

    cnt = n//L
    bunsi = dp[cnt]
    for i in range(cnt*L+1, n+1):
        bunsi = bunsi * i % mod
    cnt = k//L
    bunbo = dp[cnt]
    for i in range(cnt*L+1, k+1):
        bunbo = bunbo * i % mod
    cnt = (n-k)//L
    bunbo = bunbo * dp[cnt] % mod
    for i in range(cnt*L+1, (n-k)+1):
        bunbo = bunbo * i % mod
    ans = bunsi * pow(bunbo, mod-2, mod) % mod
    return ans

import sys
input = sys.stdin.readline
MOD = 998244353
N, K = map(int, input().split())
ans = nCr(N, K, MOD)
print(ans)
0