F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5372. -- [Pkusc2018]神仙的游戏

5372: [Pkusc2018]神仙的游戏

Time Limit: 50 Sec  Memory Limit: 512 MB
Submit: 110  Solved: 65
[Submit][Status][Discuss]

Description

小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表示按位异或。
但是不巧,在某一次游戏中,他们口算出的校验值并不一样,他们希望你帮助他们来计算一个正确的校验值。
当然,他们不强迫你口算,可以编程解决。

Input

一个串s,保证每个字符都是0,1,或者?
∣s∣<=5*10^5

Output

输出字符串的校验值,即(f(1)*12)xor(f(2)*22)xor(f(3)*32)xor…xor(f(n)*n2)

Sample Input

1?0?

Sample Output

17
将问号填充为1001,则这个串有长度为1的border,故f(1)=1
将问号填充为1010,则这个串有长度为4的border,故f(4)=1
对于f(2)和f(3),可以枚举填充的字符是什么来证明他们的值是0。
故答案是1^2 xor 4^2=17

HINT

Source

[Submit][Status][Discuss]

HOME Back