結果

問題 No.2791 Beginner Contest
ユーザー Mottchan
提出日時 2025-08-24 17:50:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 947 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 56,804 KB
最終ジャッジ日時 2025-08-24 17:50:28
合計ジャッジ時間 2,862 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

# DFS + メモ化で O(N) で解く版
from functools import lru_cache

MOD = 998244353

def count_ways(N: int, K: int) -> int:
    """
    f(i): ちょうど i に到達して終わる通り数（i>=0）
    S(x): f(0)+...+f(x) の累積和（x>=0）
    目的: 答え = S(N) (どこで終わっても良い総数)
    ただし f(0)=1, f(1..K-1)=0, f(i)=S(i-K) (i>=K)
    """

    @lru_cache(maxsize=None)
    def f(i: int) -> int:
        if i == 0:
            return 1
        if i < 0:
            return 0
        if i < K:
            return 0
        # 漸化式: f(i) = S(i-K)
        return S(i - K) % MOD

    @lru_cache(maxsize=None)
    def S(x: int) -> int:
        if x < 0:
            return 0
        # 累積和: S(x) = S(x-1) + f(x)
        return (S(x - 1) + f(x)) % MOD

    return S(N) % MOD


# --- 使い方例 ---
if __name__ == "__main__":
    N, K = 10, 3
    print(count_ways(N, K))  # 例: 出力（法 998244353）
0