結果

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

ソースコード

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())
    fact, invf = precompute_fact(2*N)
    total = comb(2*N, N, fact, invf)

    # M = K-1 までの振幅を「bad」とし、これを全体から引く
    M = K - 1
    L = 2 * K      # 反射の周期
    R = (2*N)//L + 1

    bad = 0
    for r in range(-R, R+1):
        sign = -1 if (r % 2) else 1
        a = comb(2*N, N + r*L, fact, invf)
        b = comb(2*N, N + r*L + M, fact, invf)
        bad = (bad + sign * (a - b)) % MOD

    ans = (total - bad) % MOD
    print(ans)

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