【集训队互测2017】序列计数 - 题目

给定一个仅由0和1组成的数列 ${a_{0}, a_{1}, \dots, a_{n - 1}}$ 。求有多少个仅有0和1组成的长度在 $1$ 到 $n$ 之间的数列 ${b_{0}, b_{1}, \dots, b_{m - 1}}$ ，使得对于任意 $0 \leq p \leq n - m$ ， $\sum_{k = 0}^{m - 1} a_{p + k} \land b_{k}$ 均为偶数。

答案对1000000007取模。

输入格式

一行一个01串，表示数列 $a$ ，从左到右的第 $k$ 个字符表示 $a_{k}$ 。

输出格式

一行一个整数表示数列 $b$ 的个数对1000000007取模的值。

样例一

input

00101110101110101011

output

样例二

input

00001100100101110011110011100010011010101011001010

output

932640914

限制与约定

每组测试数据的限制与约定如下所示：

测试点编号	$n$
1	$n \leq 20$
2	$n \leq 20$
3	$n \leq 100$
4
5
6
7	$n \leq 5000$
8
9
10
11
12
13	$n \leq 50000$
14
15
16
17
18
19
20

对于全部数据 $1 \leq n \leq 50000$ ，输入数据中的串是一个01串。

时间限制： $1 s$

空间限制： $1024 MB$

下载

样例数据及题解下载

来源

matthew99

Universal Online Judge

UOJ

#293. 【集训队互测2017】序列计数

输入格式

输出格式

样例一

input

output

样例二

input

output

限制与约定

下载

来源