#6618. 「THUPC 2019」令人难以忘记的题目名称 / game

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

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

游戏按轮进行,每一轮中:

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

{S'}_{i} = S_{i} + T_{\large(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
4 2
0 1 0 1
样例输出 1
2
样例说明 1

一种可能的游戏情形是:

  • 第一轮 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 查看。