#PQJ1971x10352. QOJ 1971_10352
QOJ 1971_10352
标题: 序列计数 - Problem - QOJ.ac
#10352. 序列计数
The problem was used in the following contests:
给定一个仅由 0 和 1 组成的数列{a0,a1,⋯,an−1}。求有多少个仅有0和1组成的长度在 1 到 n 之间的数列 {b0,b1,⋯,bm−1},使得对于任意 0≤p≤n−m,∑k=0m−1ap+k∧bk均为偶数。
答案对 1000000007 取模。
输入格式
一行一个 01 串,表示数列 a,从左到右的第 k 个字符表示 ak。
输出格式
一行一个整数表示数列 b 的个数对 1000000007 取模的值。
样例一
input
00101110101110101011
output
699063
样例二
input
00001100100101110011110011100010011010101011001010
output
932640914
限制与约定
每组测试数据的限制与约定如下所示:
测试点编号 n 1n≤20 2 3n≤100 4 5 6 7n≤5000 8 9 10 11 12 13n≤50000 14 15 16 17 18 19 20
对于全部数据1≤n≤50000,输入数据中的串是一个01串。