Universal Cup Judging System

Universal Cup

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

Andriana 原本有一個美麗的循環陣列 $a = (a_0, a_1, \dots, a_{n-1})$,包含 $n$ 個整數,且對於所有 $0 \le i < n$ 均滿足 $0 \le a_i < 2^b$,但不幸的是她弄丟了它!不過對我們來說,這相當幸運,因為如果沒有這些健忘的主角,世界上就會少很多重構問題。

同時,Andriana 的朋友 Bob 有一些有用的資訊:他有一本筆記本,記錄了 Andriana 陣列中連續區間的按位元與(AND)值。有一天 Bob 非常無聊,因此他針對每個位置 $i$ 與某個固定長度 $k$($k \le n$)寫下了以下數值: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (因為陣列是循環的,所以索引對 $n$ 取模)。目前不清楚 Bob 是否透過合法途徑取得這些 AND 值。

Andriana 想知道,使得 Bob 的筆記本包含足夠資訊來唯一重構出她珍貴的原始陣列的最大 $k$ 值是多少?

輸入格式

輸入的第一行包含兩個整數 $n$ 和 $b$,其中 $n$ 是 Andriana 遺失的陣列長度,$b$ 是定義限制條件 $0 \le a_i < 2^b$ 的參數。 第二行包含 $n$ 個整數 $a_i$ —— 循環陣列的元素。

輸出格式

輸出一個整數 —— 能從區間 AND 陣列 $x$ 唯一重構出陣列 $a$ 的最大 $k$ 值。

資料範圍

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

範例

輸入格式 1

6 3
7 3 7 7 3 7

輸出格式 1

2

說明

在範例中,$n = 6, b = 3$。陣列 $a = [7, 3, 7, 7, 3, 7]$ 的二進位表示為 $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$,每個元素使用三個位元。

當 $k = 2$ 時,陣列 $x$ 會是 $[3, 3, 7, 3, 3, 7]$(其中 $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$)。由陣列 $x$ 與 $b$ 的值,我們可以唯一重構出 $a$。

當 $k = 3$ 時,陣列 $x$ 會是 $[3, 3, 3, 3, 3, 3]$,這無法唯一確定 $a$(例如 $[3, 3, 7, 3, 7, 7]$ 也會得到相同的 $x$)。

因此,對於此範例,答案為 $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.