CF1184A2 Heidi Learns Hashing (Medium)

在学习了多项式哈希之后，Heidi 决定了解一下移位异或哈希。她遇到了这样一个有趣的问题。 给定一个长度为 $n$ 的二进制字符串 $y \in \{0,1\}^n$，求有多少个不同的 $k$（$0 \leq k < n$）满足存在 $x \in \{0,1\}^n$，使得 $y = x \oplus \mbox{shift}^k(x)$。 其中，$\oplus$ 表示按位异或操作，$\mbox{shift}^k$ 表示将一个二进制字符串循环右移 $k$ 位的操作。例如，$001 \oplus 111 = 110$，$\mbox{shift}^3(00010010111000) = 00000010010111$。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示二进制字符串 $y$ 的长度。 第二行包含二进制字符串 $y$。

输出一个整数，表示满足条件的 $k$ 的个数。

在第一个样例中： - $1100\oplus \mbox{shift}^1(1100) = 1010$ - $1000\oplus \mbox{shift}^2(1000) = 1010$ - $0110\oplus \mbox{shift}^3(0110) = 1010$ 不存在 $x$ 使得 $x \oplus x = 1010$，因此答案为 $3$。 由 ChatGPT 4.1 翻译