CF1184A2.Heidi Learns Hashing (Medium)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```
输入#2
```
16
```
输出#2
```
NO
```

说明/提示

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$ .

首页