結果

問題 No.2807 Have Another Go (Easy)
ユーザー gew1fw
提出日時 2025-06-12 18:57:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,568 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 272,280 KB
最終ジャッジ日時 2025-06-12 18:57:51
合計ジャッジ時間 5,748 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 total paths
    max_x = 2*N -1
    dp_total = [0]*(max_x +1)
    dp_total[0] = 1  # initial x=0, appended to Y
    total = 0
    for x in range(max_x +1):
        if dp_total[x] ==0:
            continue
        # Compute the number of d that make x+d >=2N
        min_d = max(1, 2*N -x)
        if min_d <=6:
            cnt = 6 - min_d +1
            total = (total + dp_total[x] * cnt) % MOD
        # Add transitions to x+d <2N
        for d in range(1, 6+1):
            new_x = x +d
            if new_x >=2*N:
                continue
            if new_x > max_x:
                continue
            dp_total[new_x] = (dp_total[new_x] + dp_total[x]) % MOD
    
    # Precompute for each C_i
    results = []
    for ci in C:
        # Forbidden paths: never have any x in Y (after 0) congruent to ci mod N
        # Y includes 0, which is allowed since ci >=1
        # We need to compute paths where all x in Y (after 0) are not congruent to ci mod N
        # Use DP with states (a, r) where a is 0 or 1 (x = a*N +r)
        dp0 = [0]*N
        dp1 = [0]*N
        dp0[0] = 1  # initial state: x=0, which is allowed
        forbidden_total = 0
        for _ in range(2*N +6):  # enough steps to reach 2N
            new_dp0 = [0]*N
            new_dp1 = [0]*N
            new_forbidden = 0
            # Process a=0
            for r in range(N):
                if r == ci:
                    continue
                cnt = dp0[r]
                if cnt ==0:
                    continue
                for d in range(1,7):
                    new_x = 0*N + r +d
                    if new_x >=2*N:
                        new_forbidden = (new_forbidden + cnt) % MOD
                    else:
                        a_new = new_x // N
                        r_new = new_x % N
                        if r_new == ci:
                            continue
                        if a_new ==0:
                            new_dp0[r_new] = (new_dp0[r_new] + cnt) % MOD
                        else:
                            new_dp1[r_new] = (new_dp1[r_new] + cnt) % MOD
            # Process a=1
            for r in range(N):
                if r == ci:
                    continue
                cnt = dp1[r]
                if cnt ==0:
                    continue
                for d in range(1,7):
                    new_x = 1*N + r +d
                    if new_x >=2*N:
                        new_forbidden = (new_forbidden + cnt) % MOD
                    else:
                        a_new = new_x // N
                        r_new = new_x % N
                        if r_new == ci:
                            continue
                        if a_new ==0:
                            new_dp0[r_new] = (new_dp0[r_new] + cnt) % MOD
                        else:
                            new_dp1[r_new] = (new_dp1[r_new] + cnt) % MOD
            forbidden_total = (forbidden_total + new_forbidden) % MOD
            dp0, new_dp0 = new_dp0, dp0
            dp1, new_dp1 = new_dp1, dp1
            # Check if no more changes
            if sum(dp0) + sum(dp1) + new_forbidden ==0:
                break
        ans = (total - forbidden_total) % MOD
        results.append(ans)
    
    for res in results:
        print(res)
        
if __name__ == "__main__":
    main()
0