Universal Cup Judging System

Universal Cup

时间限制: 1.0 s 内存限制: 512 MB 总分: 100
统计

Andriana possédait un magnifique tableau cyclique $a = (a_0, a_1, \dots, a_{n-1})$ de $n$ entiers, où $0 \le a_i < 2^b$ pour tout $0 \le i < n$, mais elle l'a malheureusement perdu ! Cependant, pour nous, c'est plutôt une chance, car sans ces protagonistes distraits, le monde compterait beaucoup moins de problèmes de reconstruction.

Pendant ce temps, Bob, l'ami d'Andriana, dispose d'informations utiles : il a conservé un carnet dans lequel il a noté les valeurs du ET bit à bit (AND) de segments consécutifs du tableau d'Andriana. Un jour où Bob s'ennuyait passablement, il a écrit, pour chaque position $i$ et une certaine longueur fixe $k$ ($k \le n$), la valeur $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (où les indices sont pris modulo $n$, puisque le tableau est cyclique). On ignore si Bob a obtenu ces valeurs AND par des moyens légaux.

Andriana aimerait savoir quelle est la plus grande valeur de $k$ telle que le carnet de Bob contienne suffisamment d'informations pour reconstruire de manière unique son précieux tableau d'origine.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $b$, où $n$ est la longueur du tableau perdu d'Andriana et $b$ est le paramètre définissant la contrainte $0 \le a_i < 2^b$. La deuxième ligne contient $n$ entiers $a_i$ — les éléments du tableau cyclique.

Sortie

Affichez un seul entier — la plus grande valeur de $k$ telle que le tableau $a$ puisse être reconstruit de manière unique à partir du tableau $x$ des AND de segments.

Contraintes

$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.

Exemples

Entrée 1

6 3
7 3 7 7 3 7

Sortie 1

2

Remarque

Dans l'exemple, $n = 6, b = 3$. Le tableau $a = [7, 3, 7, 7, 3, 7]$ a pour représentation binaire $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, en utilisant trois bits pour chaque élément.

Pour $k = 2$, le tableau $x$ serait $[3, 3, 7, 3, 3, 7]$ (où $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). À partir du tableau $x$ et de la valeur de $b$, nous pouvons reconstruire $a$ de manière unique.

Pour $k = 3$, le tableau $x$ serait $[3, 3, 3, 3, 3, 3]$, ce qui ne détermine pas $a$ de manière unique (par exemple, $[3, 3, 7, 3, 7, 7]$ donnerait le même $x$).

Par conséquent, pour cet exemple, la réponse est $k = 2$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.