結果

問題 No.2807 Have Another Go (Easy)
ユーザー lam6er
提出日時 2025-04-15 22:40:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,666 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,004 KB
実行使用メモリ 204,704 KB
最終ジャッジ日時 2025-04-15 22:42:09
合計ジャッジ時間 5,017 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 the total number of valid sequences
    # This is the sum over s=2N-6 to 2N-1 of ways_total[s] * (s +7 -2N)
    # Compute ways_total using dynamic programming
    max_s_total = 2 * N -1
    ways_total = [0] * (max_s_total +1)
    ways_total[0] =1
    for s in range(1, max_s_total +1):
        for d in range(1,7):
            if s -d >=0:
                ways_total[s] = (ways_total[s] + ways_total[s-d]) % MOD
    
    total_valid =0
    for s in range(max(0, 2*N -6), 2*N):
        if s > max_s_total:
            continue
        cnt = ways_total[s]
        d_min = 2*N -s
        if d_min <1:
            valid_d =6
        elif d_min >6:
            valid_d =0
        else:
            valid_d =6 -d_min +1
        total_valid = (total_valid + cnt * valid_d) % MOD
    
    # For each query C, compute the forbidden count
    for C in Cs:
        # Initialize DP
        dp = [[0]*N for _ in range(2)]
        dp[0][0] =1  # start at sum 0 (a=0, r=0)
        
        # Precompute transitions for a=0 and a=1
        # We need to process sums up to 2N-1
        max_s = 2*N -1
        for s in range(0, max_s +1):
            for a in [0,1]:
                r = s - a*N
                if a ==0 and s >=N:
                    continue
                if a ==1 and (s <N or s >=2*N):
                    continue
                if r <0 or r >=N:
                    continue
                current = dp[a][r]
                if current ==0:
                    continue
                # Try adding d=1..6
                for d in range(1,7):
                    new_s = s +d
                    if new_s >=2*N:
                        continue  # handled in forbidden count
                    new_a = new_s // N
                    new_r = new_s % N
                    if new_a >=2:
                        continue
                    if new_r == C:
                        continue
                    dp[new_a][new_r] = (dp[new_a][new_r] + current) % MOD
        
        # Compute forbidden count
        forbidden =0
        for r in range(N-6, N):
            if r <0:
                continue
            s = N +r
            if s >=2*N:
                continue
            valid_d = max(0, r +7 -N)
            forbidden = (forbidden + dp[1][r] * valid_d) % MOD
        
        ans = (total_valid - forbidden) % MOD
        print(ans)
    
if __name__ == "__main__":
    main()
0