結果
問題 | No.663 セルオートマトンの逆操作 |
ユーザー |
![]() |
提出日時 | 2025-03-20 12:35:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 3,097 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 76,804 KB |
最終ジャッジ日時 | 2025-03-20 12:35:54 |
合計ジャッジ時間 | 3,084 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 e = [] for _ in range(N): e.append(int(input[idx])) idx += 1 ans = 0 # Iterate over all possible initial pairs (a0, a1) for a0 in [0, 1]: for a1 in [0, 1]: # dp_prev represents the current state of (previous, current) dp_prev = {(a0, a1): 1} valid = True # Process each step to build up the array up to a_{N-1} for step in range(N - 2): current_e = e[step + 1] dp_next = {} for (prev_prev, prev), cnt in dp_prev.items(): possible_curr = [] for curr in [0, 1]: # Check if (prev_prev, prev, curr) produces current_e if current_e == 0: if (prev == 0 and curr == 0) or (prev_prev == 1 and prev == 1 and curr == 1): possible_curr.append(curr) else: if not ((prev == 0 and curr == 0) or (prev_prev == 1 and prev == 1 and curr == 1)): possible_curr.append(curr) if not possible_curr: continue for curr in possible_curr: key = (prev, curr) if key in dp_next: dp_next[key] = (dp_next[key] + cnt) % MOD else: dp_next[key] = cnt % MOD if not dp_next: valid = False break dp_prev = dp_next if not valid: continue # Check the remaining two conditions after processing all steps total = 0 for (p, q), cnt in dp_prev.items(): # Check condition for e[N-1] (triplet (p, q, a0)) check1 = False target_e = e[-1] if target_e == 0: if (q == 0 and a0 == 0) or (p == 1 and q == 1 and a0 == 1): check1 = True else: if not ((q == 0 and a0 == 0) or (p == 1 and q == 1 and a0 == 1)): check1 = True # Check condition for e[0] (triplet (q, a0, a1)) check2 = False target_e0 = e[0] if target_e0 == 0: if (a0 == 0 and a1 == 0) or (q == 1 and a0 == 1 and a1 == 1): check2 = True else: if not ((a0 == 0 and a1 == 0) or (q == 1 and a0 == 1 and a1 == 1)): check2 = True if check1 and check2: total = (total + cnt) % MOD ans = (ans + total) % MOD print(ans % MOD) if __name__ == '__main__': main()