結果

問題 No.2807 Have Another Go (Easy)
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:42:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,041 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 53,276 KB
最終ジャッジ日時 2025-04-15 22:43:31
合計ジャッジ時間 4,689 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    M = int(input[ptr])
    ptr +=1
    k = int(input[ptr])
    ptr +=1
    C = list(map(int, input[ptr:ptr+k]))
    ptr +=k
    
    # Compute T: total number of paths
    size = 2 * N
    dp_T = [0] * (size + 6)  # To handle up to size +6
    dp_T[0] = 1
    T = 0
    for s in range(size):
        if dp_T[s] == 0:
            continue
        for d in range(1, 7):
            new_s = s + d
            if new_s >= 2 * N:
                T = (T + dp_T[s]) % MOD
            else:
                dp_T[new_s] = (dp_T[new_s] + dp_T[s]) % MOD
    
    # Precompute for each possible c, but since c can be up to N-1, we process each query individually
    for c in C:
        c_mod = c % N
        # Initialize dp_not as two arrays for q=0 and q=1
        dp_not = [[0]*N for _ in range(2)]
        if 0 != c_mod:
            dp_not[0][0] = 1
        U = 0
        # We need to process states in order of increasing sum
        # Iterate over possible sums s from 0 to 2N-1
        for s in range(2 * N):
            q = s // N
            r = s % N
            if q >= 2:
                continue
            if q > 1:
                continue
            current = dp_not[q][r]
            if current == 0:
                continue
            if r == c_mod:
                continue
            # Roll the die
            for d in range(1, 7):
                new_s = s + d
                if new_s >= 2 * N:
                    U = (U + current) % MOD
                else:
                    new_q = new_s // N
                    new_r = (r + d) % N
                    if new_r == c_mod:
                        continue
                    if new_q >= 2:
                        continue
                    dp_not[new_q][new_r] = (dp_not[new_q][new_r] + current) % MOD
        # The answer is (T - U) mod MOD
        ans = (T - U) % MOD
        print(ans)
        
if __name__ == '__main__':
    main()
0