結果

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

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    k = int(input[idx]); idx +=1
    Cs = list(map(int, input[idx:idx+k]))
    
    # Precompute for T
    # We need to compute dp[s], sum from s=0 to 2N-1 dp[s] * count(s)
    # count(s) = max(0,7 - (2N -s)) when s >=2N-6 else 0
    
    max_s_prev = 2 * N - 1
    dp = [0] * (max_s_prev + 1)
    dp[0] = 1  # initial state
    
    for s in range(1, max_s_prev + 1):
        for d in range(1, 7):
            prev = s - d
            if prev >= 0 and prev < 2 * N:
                dp[s] = (dp[s] + dp[prev]) % MOD
    
    T = 0
    start = max(0, 2 * N - 6)
    for s in range(start, 2 * N):
        cnt = 7 - (2 * N - s)
        if cnt < 0:
            cnt = 0
        T = (T + dp[s] * cnt) % MOD
    
    # For each query C in Cs:
    for C in Cs:
        # C_i <N, handle modulo C condition
        C_val = C % N
        
        # Dynamic programming for U_i
        # States: (k, r) with k in 0,1 (kN + r), and r not equal to C_val
        # We need to compute the number of paths where all intermediate steps' r != C_val
        # and in the final step, they reach >=2N
        
        # Initialize
        dp_no = [[0] * N for _ in range(2)]
        if 0 != C_val:
            dp_no[0][0] = 1
        else:
            dp_no[0][0] = 0
        
        U = 0
        new_dp_no = [[0]*N for _ in range(2)]
        for _ in range(2 * N + 1):  # steps up to 2N
            new_dp_no = [[0]*N for _ in range(2)]
            # Accumulate contributions to U first
            for k in range(2):
                for r in range(N):
                    if dp_no[k][r] == 0:
                        continue
                    s_prev = k * N + r
                    # Compute d's that make s_prev +d >=2N
                    min_d = max(1, 2*N - s_prev)
                    if min_d >6:
                        continue  # no such d
                    max_d = 6
                    cnt_d = max_d - min_d + 1
                    U = (U + dp_no[k][r] * cnt_d) % MOD
            
            # Update transitions for states not in termination
            for k in range(2):
                for r in range(N):
                    if dp_no[k][r] == 0:
                        continue
                    s_prev = k * N + r
                    for d in range(1,7):
                        new_s = s_prev + d
                        if new_s >= 2 * N:
                            continue
                        new_k = new_s // N
                        new_r = new_s % N
                        if new_r == C_val:
                            continue
                        new_dp_no[new_k][new_r] = (new_dp_no[new_k][new_r] + dp_no[k][r]) % MOD
            # Update dp_no
            dp_no, new_dp_no = new_dp_no, dp_no
            # Check for convergence or termination after sufficient steps
            # Limited to steps up to 2*N
        
        ans = (T - U) % MOD
        print(ans)
        
if __name__ == "__main__":
    main()
0