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

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

题目描述

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

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

  • Alice 给出一个长度为 NN 的正整数序列 TT
  • Bob 看到 Alice 给出的 TT,然后选择 [0,N1][0, N-1] 里的一个整数 xx
  • 之后我们把 SS 转化为 SS',规则如下:
Si=Si+T(i+x)modN{S'}_{i} = S_{i} + T_{\large(i+x)\bmod N}
  • SS' 作为新的 SS,结束这一轮。

如果某一轮结束后,SS 中每个数都是一个给定质数 PP 的倍数,那么 Alice 胜利。

给定 NN 和初始序列 SS,请问:Alice 是否能在有限步必胜,如果答案为是,最快可以在几轮内保证胜利。

输入格式

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

接下来一行 NN 个空格隔开的整数,描述初始序列 SS (0Si109)(0\le S_i \le 10^9)

保证 N3×105N\le 3\times 10^5P200P\le 200

输出格式

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

样例

4 2
0 1 0 1
2

一种可能的游戏情形是:

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

可以证明 22 轮是最优的。

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

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