問題一覧 > 通常問題

No.663 Inverse Operation of a Cellular Automaton

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 66
作問者 : horiesiniti / テスター : はむこ
お気に入りにしたユーザー ProblemId : 1955 / 自分の提出
問題文最終更新日: 2026-06-25 14:07:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 186 (順位表) の他の問題:

Note

This problem is an original problem that I published on HackerRank, reposted on this page with the permission of both HackerRank and yukicoder.

Problem Statement

There is a thing called a cellular automaton.
It is a system in which a map is divided into cells, and the next state of every cell is determined by the states of its neighboring cells.
The simplest kind of cellular automaton is the one-dimensional one.
In a one-dimensional cellular automaton, 0s and 1s are arranged in a single row on the upper level, and the 0s and 1s of the next level are determined from the 0s and 1s of the upper level.
Among these, let us consider the one whose cells take the values 0 and 1, known as Rule 110.
You are given the second level, which is the result of applying the one-dimensional cellular automaton Rule 110 to the first level. Write a program that outputs the number of possible first levels.
In both the first and second levels, the right end and the left end are connected, and the first and second levels have the same number of columns.

The figure illustrates the determination rule of the one-dimensional cellular automaton Rule 110, focusing only on the cell being computed in the second level.
In words:
  • If all three cells are 1, the result is 0.
  • If the center and the right cells are 0, the result is 0.
  • Otherwise, the result is 1.
Each 0 or 1 in the second level is determined from three values in the first level: the left, center, and right. An example of a first level and a second level. The second level is determined from the first level. Note that the left and right ends are connected.

Example

First level 00010111

Second level 00111101

Input

N
$e_1$
$\dots$
$e_i$
$\dots$
$e_n$

N is the number of columns. $4 \le N \le 2000$
$e_i$ describes whether the $i$-th column of the second level is 0 or 1.

Output

$ans$
Output $ans$, the number of first levels that can generate the second level, modulo $10^9+7$. Print a newline at the end.

Sample

Sample 1
Input
4
0
0
0
0
Output
2

The only possible first levels are 0000 and 1111.

Sample 2
Input
11
0
1
1
0
1
1
0
1
1
1
0
Output
2

Sample 3
Input
6
1
1
1
1
0
1
Output
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。