結果
問題 | No.2807 Have Another Go (Easy) |
ユーザー |
![]() |
提出日時 | 2025-04-15 22:39:09 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,666 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 52,280 KB |
最終ジャッジ日時 | 2025-04-15 22:40:45 |
合計ジャッジ時間 | 4,869 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 44 |
ソースコード
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()