結果

問題 No.2807 Have Another Go (Easy)
ユーザー lam6er
提出日時 2025-04-15 22:46:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,741 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 81,460 KB
実行使用メモリ 52,496 KB
最終ジャッジ日時 2025-04-15 22:48:34
合計ジャッジ時間 4,678 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    total_dp = [0] * (2*N)
    total = 0
    total_dp[0] = 1
    for s in range(2*N):
        if total_dp[s] == 0:
            continue
        for d in range(1,7):
            new_s = s + d
            if new_s >= 2*N:
                total = (total + total_dp[s]) % MOD
            else:
                total_dp[new_s] = (total_dp[new_s] + total_dp[s]) % MOD
    
    # Precompute ways_from[s] for all s < 2N
    ways_from = [0] * (2*N)
    for s in reversed(range(2*N)):
        cnt = 0
        for d in range(1,7):
            if s + d >= 2*N:
                cnt +=1
            else:
                cnt += ways_from[s + d]
                cnt %= MOD
        ways_from[s] = cnt % MOD
    
    # Process each query
    for c in C:
        r = c % N
        forbidden_dp = [0] * (2*N)
        if 0 % N != r:
            forbidden_dp[0] = 1
        forbidden_total = 0
        for s in range(2*N):
            if forbidden_dp[s] == 0:
                continue
            if s % N == r:
                continue
            for d in range(1,7):
                new_s = s + d
                if new_s >= 2*N:
                    forbidden_total = (forbidden_total + forbidden_dp[s]) % MOD
                else:
                    if new_s % N != r:
                        forbidden_dp[new_s] = (forbidden_dp[new_s] + forbidden_dp[s]) % MOD
        ans = (total - forbidden_total) % MOD
        print(ans)
        
if __name__ == "__main__":
    main()
0