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