結果

問題 No.2807 Have Another Go (Easy)
ユーザー lam6er
提出日時 2025-03-31 17:57:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,036 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 52,476 KB
最終ジャッジ日時 2025-03-31 17:58:38
合計ジャッジ時間 4,751 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = 2
    k = int(data[2])
    Cs = list(map(int, data[3:3+k]))
    
    # Precompute the total_sequences
    max_sum = 2 * N + 6
    dp = [0] * (max_sum + 1)
    dp[0] = 1
    total_sequences = 0
    for s in range(0, 2 * N):
        current = dp[s]
        if current == 0:
            continue
        for D in range(1, 7):
            new_s = s + D
            if new_s >= 2 * N:
                total_sequences = (total_sequences + current) % MOD
            else:
                dp[new_s] = (dp[new_s] + current) % MOD
        dp[s] = 0
    
    # Process each query Ci
    for Ci in Cs:
        forbidden_count = 0
        F0 = [0] * N
        F1 = [0] * N
        F0[0] = 1
        
        for s in range(N):
            current = F0[s]
            if current == 0:
                continue
            for D in range(1, 7):
                new_s = s + D
                if new_s >= 2 * N:
                    forbidden_count = (forbidden_count + current) % MOD
                else:
                    if new_s < N:
                        if new_s != Ci:
                            F0[new_s] = (F0[new_s] + current) % MOD
                    else:
                        new_b = new_s - N
                        if new_b != Ci:
                            F1[new_b] = (F1[new_b] + current) % MOD
        
        for b in range(N):
            current = F1[b]
            if current == 0:
                continue
            s_in_a1 = N + b
            for D in range(1, 7):
                new_s = s_in_a1 + D
                if new_s >= 2 * N:
                    forbidden_count = (forbidden_count + current) % MOD
                else:
                    new_b = b + D
                    if new_b != Ci:
                        F1[new_b] = (F1[new_b] + current) % MOD
        
        ans = (total_sequences - forbidden_count) % MOD
        print(ans)

if __name__ == '__main__':
    main()
0