我搬运我自己应该算原创吧

题目

• 题意
• 题解

题意

设$f(x)$为$x$二进制下$1$的个数. 给出长度为$m$的$01$序列$a$, 给出$L$, 求有多少个$x\in [0,L]$, 满足$f(x+i)\mathrm{m}\mathrm{o}\mathrm{d}2=a_i$

$1\le m\le 100,0\le L\le 10^{18}$

题解

设$g(i)=f(i)\mathrm{m}\mathrm{o}\mathrm{d}2$

我们把$g(i)$求出$[0,L+m]$个, 排成一排, 然后就类似于字符串匹配一样统计个数.

注意到$L$很大, 我们没办法把这个序列全部求出来. 所以这个序列一定有规律.

注意到, 当$i\in [2^{k?1},2^k)$时, 有$f(i+2^k)=f(i)+1$, 也就是相当于$i$的二进制下的第$k$位从$0$变成$1$, 所以有$g(i+2^k)=g(i)\oplus 1$. 这样, 我们就发现了序列$g$的构造方式:

第一个是0, 然后把当前序列取反, 拼在后面. 如下:

0
01
0110
01101001
0110100110010110
...