No.663 Inverse Operation of a Cellular Automaton
タグ : / 解いたユーザー数 66
作問者 :
horiesiniti
/ テスター :
はむこ
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.
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。