結果

問題 No.2807 Have Another Go (Easy)
ユーザー gew1fw
提出日時 2025-06-12 13:14:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,784 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 272,204 KB
最終ジャッジ日時 2025-06-12 13:16:58
合計ジャッジ時間 4,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    Cs = list(map(int, input[ptr:ptr+k]))
    ptr +=k
    
    # Precompute powers of 6 modulo MOD
    max_power = 2*N + 6
    pow6 = [1] * (max_power +1)
    for i in range(1, max_power+1):
        pow6[i] = pow6[i-1] *6 % MOD
    
    # Compute T: total number of valid sequences
    T = 0
    dp = [0]*(2*N)
    dp[0] = 1
    for a in range(2*N):
        if dp[a] ==0:
            continue
        for d in range(1,7):
            new_a = a +d
            if new_a >= 2*N:
                T = (T + dp[a] * pow6[0]) % MOD  # pow6[0] is 1, since no more steps
            else:
                dp[new_a] = (dp[new_a] + dp[a]) % MOD
    
    # For each query Ci, compute S_i and output (T - S_i) mod MOD
    for c in Cs:
        # DP for S_i: sequences that never hit c mod N
        dp0 = [0]*(2*N)
        dp0[0] = 1
        S = 0
        for a in range(2*N):
            if dp0[a] ==0:
                continue
            # Check if current a is a starting X of a step, which is added to Y
            # The starting X is a, so check a mod N != c
            if a % N == c:
                dp0[a] =0  # invalidate this state
                continue
            for d in range(1,7):
                new_a = a +d
                if new_a >= 2*N:
                    S = (S + dp0[a]) % MOD
                else:
                    # Check if the next step's starting X (new_a) mod N is not c
                    if new_a % N != c:
                        dp0[new_a] = (dp0[new_a] + dp0[a]) % MOD
        ans = (T - S) % MOD
        print(ans)
        
if __name__ == '__main__':
    main()
0