結果

問題 No.2807 Have Another Go (Easy)
ユーザー gew1fw
提出日時 2025-06-12 16:37:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,073 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 270,208 KB
最終ジャッジ日時 2025-06-12 16:37:36
合計ジャッジ時間 4,947 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    N, M, k = map(int, sys.stdin.readline().split())
    Cs = list(map(int, sys.stdin.readline().split()))
    MOD = 998244353

    max_s = 2 * N
    f = [0] * (max_s + 7)  # s can be up to max_s +6

    # Base case: s >= 2*N
    for s in range(2*N, 2*N +7):
        f[s] = 1

    # Compute f[s] for s from 2*N -1 down to 0
    for s in range(2*N -1, -1, -1):
        total = 0
        for d in range(1,7):
            if s + d >= len(f):
                fsd = 1  # since s +d >=2*N
            else:
                fsd = f[s + d]
            total += fsd
            if total >= MOD:
                total -= MOD
        f[s] = total % MOD

    A = f[0]

    # Now, for each Ci, compute B
    for Ci in Cs:
        Ci_mod = Ci % N

        # Create a new DP for B, avoiding states where s mod N == Ci_mod
        # We compute fB[s], where fB[s] is the number of ways to reach >=2N from s without hitting any state with s' mod N == Ci_mod

        # Since the forbidden states are s ≡ Ci_mod mod N, we need to compute fB[s] for s < 2*N

        # Initialize fB[s] =0 for s >=2*N
        fB = [0] * (max_s +7)
        for s in range(2*N, 2*N +7):
            fB[s] = 1

        # Compute fB[s] for s from 2*N -1 down to 0
        # For each s, if s mod N == Ci_mod: fB[s] =0
        # else: fB[s] = sum_{d=1-6} fB[s+d] if s +d <2*N; else 1

        # We precompute fB[s] for all s
        for s in range(2*N -1, -1, -1):
            if s % N == Ci_mod:
                fB[s] = 0
                continue

            total = 0
            for d in range(1,7):
                if s + d >= 2*N:
                    contrib = 1
                else:
                    if (s + d) >= len(fB):
                        contrib = 1
                    else:
                        contrib = fB[s + d]
                total += contrib
                if total >= MOD:
                    total -= MOD
            fB[s] = total % MOD

        B = fB[0]
        ans = (A - B) % MOD
        print(ans)

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