結果

問題 No.663 セルオートマトンの逆操作
ユーザー lam6er
提出日時 2025-03-20 20:53:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 3,097 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 76,852 KB
最終ジャッジ日時 2025-03-20 20:53:47
合計ジャッジ時間 2,667 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0