#6436. 「PKUSC2018」神仙的游戏

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

小 D 和小 H 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏,比如「口算一个 44 位数是不是完全平方数」。

今天他们发现了一种新的游戏:首先称 ss 长度为 len\rm len 的前缀成为 border 当且仅当 s[1len]=s[slen+1s]s[1\dots \text {len} ] = s[|s|-\text {len} + 1\dots |s|] 。给出一个由 01? 组成的字符串 ss, 将 ss 中的问号用变成 01 替换,对每个 len\rm len 口算是否存在替换问号的方案使得 ss 长度为 len\rm len 的前缀成为 border,把这个结果记做 f(len){0,1}f(\text{len})\in \{0,1\}f(len)=1f(\text{len}) = 1 如果 ss 长度为 len\rm len 的前缀能够成为 border,否则 f(len)=0f(\text{len}) = 0

由于小 D 和小 H 是神仙,所以他们计算的 ss 的长度很长,因此把计算的结果一一比对会花费很长的时间。为了方便比对,他们规定了一个校验值:(f(1)×12) xor (f(2)×22) xor (f(3)×32) xor  xor (f(n)×n2)(f(1)\times 1^2)~\text{xor}~(f(2)\times 2^2)~\text{xor}~(f(3)\times 3^2)~\text{xor}~\dots~\text{xor}~(f(n)\times n^2) 来校验他们的答案是否相同。xor 表示按位异或。但是不巧,在某一次游戏中,他们口算出的校验值并不一样,他们希望你帮助他们来计算一个正确的校验值。当然,他们不强迫你口算,可以编程解决。

输入格式

一个串 ss, 保证每个字符都是 0,1,或者?.

输出格式

输出字符串的校验值, 即 (f(1)×12) xor (f(2)×22) xor (f(3)×32) xor  xor (f(n)×n2)(f(1)\times 1^2)~\text{xor}~(f(2)\times 2^2)~\text{xor}~(f(3)\times 3^2)~\text{xor}~\dots~\text{xor}~(f(n)\times n^2)

样例

样例输入

1?0?

样例输出

17

样例解释

将问号填充为 1001,则这个串有长度为 11 的 border, 故 f(1)=1f(1) = 1

将问号填充为 1101,则这个串有长度为 44 的 border, 故 f(4)=1f(4) = 1

对于 f(2)f(2)f(3)f(3),可以枚举填充的字符是什么来证明他们的值是 0。

故答案是12 xor 42=171^2~\text{xor}~4^2=17

数据范围与提示

本题采用捆绑测试,我们将测试点分成若干个 subtask,对于一个 subtask,只有通过这个 subtask 的所有测试点才能拿到这个 subtask 的分数。每个 subtask 的限制如下:

子任务编号 s\lvert s \rvert 附加说明 分数
1 1000\leq 1000 8
2 5×105\leq 5 \times 10^5 输入的串没有问号 10
3 5×105\leq 5\times 10^5 数据随机 22
4 5×105\leq 5\times 10^5 问号个数至少是s5000\lvert s \rvert -5000 27
5 5×105\leq 5\times 10^5 33