#XMOJ12647. 元胞自动机的逆操作
元胞自动机的逆操作
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:am.in 输出文件:am.out
元胞自动机是一种将地图划分为格子,每个格子的下一状态由相邻格子状态决定的系统。
我们考虑最简单的一维元胞自动机,格子的值只有 $0$ 和 $1$,使用 110 规则。
给定第二行(经过一次 110 变换后的结果),求有多少种可能的第一行,满足:
- 第一行、第二行长度相同,都是环形(左右两端相连)
- 对第一行应用 110 规则恰好得到第二行
110 规则(输入三元组 $(a,b,c)$ 是第一行相邻三个格子,输出 $e$ 是第二行对应位置):
- 如果 $a=1,b=1,c=1$,则 $e=0$
- 如果 $b=0,c=0$,则 $e=0$
- 其余情况,$e=1$
> 等价 110 规则真值表(三元组 $abc → e$)
> 000 → 0
> 001 → 1
> 010 → 1
> 011 → 1
> 100 → 0
> 101 → 1
> 110 → 1
> 111 → 0
输入格式
第一行一个整数 $N$。
接下来 $N$ 行,每行一个整数 $e_i$,代表第二行第 $i$ 位的值。
输出格式
输出合法的第一行方案数,对 $10^9+7$ 取模。
样例
样例 1
4
0
0
0
0
2
样例说明:
合法的第一行只有 0000 和 1111。
样例 2
11
0
1
1
0
1
1
0
1
1
1
0
2
样例 3
6
1
1
1
1
0
1
3
数据范围
对于 35% 的数据,$N \le 5$。
对于 70% 的数据,$N \le 100$。
对于 100% 的数据,$4 \le N \le 2000$,$e_i \in \{0,1\}$。
相关
在下列比赛中: