結果

問題 No.1970 ひよこ鑑定士
コンテスト
ユーザー 57tggx
提出日時 2025-05-22 12:38:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,637 bytes
コンパイル時間 640 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 41,828 KB
最終ジャッジ日時 2025-05-22 12:38:22
合計ジャッジ時間 4,913 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
MOD = 998244353

def precompute_fact(n):
    fact = [1] * (n+1)
    invf = [1] * (n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1] * i % MOD
    invf[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        invf[i-1] = invf[i] * i % MOD
    return fact, invf

def comb(n, k, fact, invf):
    if k < 0 or k > n:
        return 0
    return fact[n] * invf[k] % MOD * invf[n-k] % MOD

def main():
    N, K = map(int, input().split())
    # 1) Precompute factorials up to 2N
    fact, invf = precompute_fact(2*N)
    C2N_N = comb(2*N, N, fact, invf)

    # 2) M = K-1 として，幅 M を超えない「補集合」の数を反射法で求める
    M = K - 1
    D = M + 1  # 反射周期

    # （反射法の詳細はコード内コメントをご参照ください）
    # 整数 r を -∞..∞ で動かすのではなく，実際に 2N 以下の項だけを走査します。
    # r ごとに項 C(2N, N + r*D) を足し，
    # 「次の境界」（幅を超える: +M+1）に反射させた分を引きます。
    comp = 0
    # r の範囲: N + r*D ∈ [0..2N] より
    r_min = (-N) // D
    r_max =  (2*N - N) // D
    for r in range(r_min, r_max+1):
        base = N + r*D
        # 「ずばり幅内」のパス：C(2N, base)
        add = comb(2*N, base, fact, invf)
        # 「一歩はみ出す」パス：C(2N, base + (M+1))
        sub = comb(2*N, base + (M+1), fact, invf)
        comp = (comp + add - sub) % MOD

    # 3) 求める答えは 全通り - 補集合
    ans = (C2N_N - comp) % MOD
    print(ans)

if __name__ == "__main__":
    main()
0