P5379.md

[THUPC2019]令人难以忘记的题目名称

题目描述

现在有一个长度为 $N$ 的整数序列 $S$（下标从 $0$ 开始），Alice 和 Bob 在这个序列上博弈。

游戏按轮进行，每一轮中：

• Alice 给出一个长度为 $N$ 的正整数序列 $T$
• Bob 看到 Alice 给出的 $T$，然后选择 $[0, N-1]$ 里的一个整数 $x$
• 之后我们把 $S$ 转化为 $S'$，规则如下：

$${S'}{i} = S{i} + T_{(i+x)\bmod N}$$

• 以 $S'$ 作为新的 $S$，结束这一轮。

如果某一轮结束后，$S$ 中每个数都是一个给定质数 $P$ 的倍数，那么 Alice 胜利。

给定 $N$ 和初始序列 $S$，请问：Alice 是否能在有限步必胜，如果答案为是，最快可以在几轮内保证胜利。

输入格式

第一行两个非负整数 $N,P$，保证 $P$ 是一个质数。

接下来一行 $N$ 个空格隔开的整数，描述初始序列 $S$（$0\le S_i \le 10^9$）。

保证 $N\le 3\times 10^5$，$P\le 200$。

输出格式

输出一个整数，如果 Alice 不能在有限步必胜，输出 $-1$，否则输出一个整数 $x$ 表示 Alice 最快能在几轮内胜利。

样例 #1

样例输入 #1

4 2
0 1 0 1

样例输出 #1

2

提示

样例解释

一种可能的游戏情形是：

• 第一轮 $T=[1, 0, 1, 0]$，$x=0$，转化后的 $S'=[1,1,1,1]$。
• 第二轮 $T=[1,1,1,1]$，无论 $x$ 取什么，转化后的 $S'=[2,2,2,2]$。

可以证明 $2$ 轮是最优的。

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。