【集训队互测2017】序列计数
给定一个仅由0和1组成的数列$\{a_0, a_1, \cdots, a_{n - 1}\}$。求有多少个仅有0和1组成的长度在$1$到$n$之间的数列$\{b_0, b_1, \cdots, b_{m - 1}\}$，使得对于任意$0 \le p \le n - m$，$\sum_{k = 0} ^ {m - 1}{a_{p + k} \wedge b_k}$均为偶数。
答案对1000000007取模。
输入格式
一行一个01串，表示数列$a$，从左到右的第$k$个字符表示$a_k$。
输出格式
一行一个整数表示数列$b$的个数对1000000007取模的值。
00101110101110101011
699063
00001100100101110011110011100010011010101011001010
932640914
限制与约定
每组测试数据的限制与约定如下所示：
| 测试点编号 | $n$ |
|---|---|
| 1 | $n \le 20$ |
| 2 | |
| 3 | $n \le 100$ |
| 4 | |
| 5 | |
| 6 | |
| 7 | $n \le 5000$ |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | $n \le 50000$ |
| 14 | |
| 15 | |
| 16 | |
| 17 | |
| 18 | |
| 19 | |
| 20 |
对于全部数据$1 \le n \le 50000$，输入数据中的串是一个01串。
时间限制：$1\texttt{s}$
空间限制：$1024\texttt{MB}$
下载
来源
matthew99