Heidi Learns Hashing (Medium)

题意翻译

- 给定一个 长度为 $n$ 的 01 串 $y$ - 我们给定一个函数 $\text{shift}$ 使得对于任意一个数 $a$，$\text{shift}^a$ 指的是对于给定的 01 串循环右移 $a$ 个字符 - 现在求满足 - $x$ 也是一个长为 $n$ 的 01 串 - $y=x\ ⊕\ \text{shift}^k(x)$ - $⊕$ 为异或 - 的 01 串个数。（上述式子的 $k$ 为 $1$ 到满足上述 01 串的个数的其中一个数，并且不能重复）

题目描述

After learning about polynomial hashing, Heidi decided to learn about shift-xor hashing. In particular, she came across this interesting problem. Given a bitstring $ y \in \{0,1\}^n $ find out the number of different $ k $ ( $ 0 \leq k < n $ ) such that there exists $ x \in \{0,1\}^n $ for which $ y = x \oplus \mbox{shift}^k(x). $ In the above, $ \oplus $ is the xor operation and $ \mbox{shift}^k $ is the operation of shifting a bitstring cyclically to the right $ k $ times. For example, $ 001 \oplus 111 = 110 $ and $ \mbox{shift}^3(00010010111000) = 00000010010111 $ .

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ), the length of the bitstring $ y $ . The second line contains the bitstring $ y $ .

输出格式

Output a single integer: the number of suitable values of $ k $ .

输入输出样例

输入样例 #1

4
1010

输出样例 #1

3

说明

In the first example: - $ 1100\oplus \mbox{shift}^1(1100) = 1010 $ - $ 1000\oplus \mbox{shift}^2(1000) = 1010 $ - $ 0110\oplus \mbox{shift}^3(0110) = 1010 $ There is no $ x $ such that $ x \oplus x = 1010 $ , hence the answer is $ 3 $ .