P5466 [PKUSC2018] Immortals' Game

Little D and Little H are two immortals. They often play games that only immortals would play, such as “mentally checking whether a 4-digit number is a perfect square”. Today they found a new game: first, for a string $s$, a prefix of length $len$ is called a border if and only if $s[1\dots len] = s[|s|-len+1\dots |s|]$. Given a string $s$ consisting of $\texttt{01?}$, replace each question mark in $s$ with $\texttt{0}$ or $\texttt{1}$. For each $len$, mentally determine whether there exists a way to replace the question marks such that the prefix of $s$ of length $len$ becomes a border, and record this result as $f(len)\in\{0,1\}$. If the prefix of $s$ of length $len$ can become a border, then $f(len)=1$; otherwise $f(len)=0$. Since Little D and Little H are immortals, the length of $s$ they compute is very large, so comparing the results one by one would take a long time. To make comparison easier, they define a checksum: $(f(1)\times 1^2)~\operatorname{xor}~(f(2)\times 2^2)~\operatorname{xor}~(f(3)\times 3^2)~\operatorname{xor}~\dots~\operatorname{xor}~(f(n)\times n^2)$ to verify whether their answers are the same. $\operatorname{xor}$ denotes bitwise XOR. Unfortunately, in one game, the checksums they computed mentally were not the same. They want you to help them compute the correct checksum. Of course, they do not force you to do it mentally; you may solve it by programming.

A string $s$, guaranteed that each character is $\texttt 0$, $\texttt 1$, or $\texttt ?$.

Output the checksum of the string, i.e. $(f(1)\times 1^2)~\operatorname{xor}~(f(2)\times 2^2)~\operatorname{xor}~(f(3)\times 3^2)~\operatorname{xor}~\dots~\operatorname{xor}~(f(n)\times n^2)$.

### Sample Explanation Fill the question marks as 1001. Then this string has a border of length 1, so $f(1)=1$. Fill the question marks as 1101. Then this string has a border of length 4, so $f(4)=1$. For $f(2)$ and $f(3)$, you can enumerate what characters are filled in to prove that their values are 0. So the answer is $1^2~\operatorname{xor}~4^2=17$. ### Constraints | Subtask ID | $\lvert s \rvert$ | Additional Notes | Score | | :--------: | :------------------: | :----------------------: | :--: | | 1 | $\leq 1000$ | None | 8 | | 2 | $\leq 5 \times 10^5$ | The input string has no question marks | 10 | | 3 | $\leq 5\times 10^5$ | The testdata is random | 22 | | 4 | $\leq 5\times 10^5$ | The number of question marks is at least $\lvert s \rvert - 5000$ | 27 | | 5 | $\leq 5\times 10^5$ | None | 33 | Translated by ChatGPT 5