[PKUSC2018]神仙的游戏
题目描述
小 $D$ 和小 $H$ 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏,比如 “口算一个 4 位数是不是完全平方数” 。
今天他们发现了一种新的游戏:首先称 $s$ 长度为 $len$ 的前缀成为 border 当且仅当 $s[1\dots len ] = s[|s|-len + 1\dots |s|]$ 。给出一个由 01? 组成的字符串 $s$, 将 $s$ 中的问号用变成 01 替换,对每个 $len$ 口算是否存在替换问号的方案使得 $s$ 长度为$len$的前缀成为 border,把这个结果记做 $f(len)\in \{0,1\}$。$f(len) = 1$如果 $s$ 长度为$len$的前缀能够成为 border,否则$f(len) = 0$。
由于小 $D$ 和小 $H$ 是神仙,所以他们计算的 $s$ 的长度很长,因此把计算的结果一一比对会花费很长的时间。为了方便比对,他们规定了一个校验值:$(f(1)\times 1^2)~xor~(f(2)\times 2^2)~xor~(f(3)\times 3^2)~xor~\dots~xor~(f(n)\times n^2)$来校验他们的答案是否相同。xor 表示按位异或。但是不巧,在某一次游戏中,他们口算出的校验值并不一样,他们希望你帮助他们来计算一个正确的校验值。当然,他们不强迫你口算,可以编程解决。
输入输出格式
输入格式
一个串 $s$, 保证每个字符都是 0,1,或者?.
输出格式
输出字符串的校验值, 即$(f(1)\times 1^2)~xor~(f(2)\times 2^2)~xor~(f(3)\times 3^2)~xor~\dots~xor~(f(n)\times n^2)$。
输入输出样例
输入样例 #1
1?0?
输出样例 #1
17
说明
### 样例解释
将问号填充为 1001,则这个串有长度为 1 的 border, 故 $f(1) = 1$。
将问号填充为 1101,则这个串有长度为 4 的 border, 故 $f(4) = 1$。
对于 $f(2)$ 和 $f(3)$,可以枚举填充的字符是什么来证明他们的值是 0。
故答案是$1^2~xor~4^2=17$
### 数据范围
| 子任务编号 | $\lvert s \rvert$ | 附加说明 | 分数 |
| :--------: | :------------------: | :----------------------: | :--: |
| 1 | $\leq 1000$ | 无 | 8 |
| 2 | $\leq 5 \times 10^5$ | 输入的串没有问号 | 10 |
| 3 | $\leq 5\times 10^5$ | 数据随机 | 22 |
| 4 | $\leq 5\times 10^5$ | 问号个数至少是$\lvert s \rvert -5000$ | 27 |
| 5 | $\leq 5\times 10^5$ | 无 | 33 |