自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 22:10:09，当前版本为作者最后更新于2019-11-06 01:31:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先既然胜利条件是“每个数都是一个给定质数 P 的倍数”，那么当然我们可以时时刻刻把 $S$ 对 $P$ 取模。

那么我们考虑最快可以在多少步内胜利：反过来考虑，什么样的序列可以在零步内胜利？当然是全 0 序列。

什么样的序列可以在一步内胜利？假设我们给出了 $T$，使得无论 Bob 怎么操作都会变成全 0，那么说明对任意的 $i,j$ 都有 $S_i+T_j=0$（加法和等于都是在 $\bmod P$ 意义下的，下同）容易发现这只在 $S_i$ 全相等时可能发生；因此一步内胜利等价于 $S_i$ 全相等。

什么样的序列可以在两步内胜利？那相当于说无论 Bob 怎么操作，序列都会变成全相等的序列。也就是说我们给出 $T$ 之后，Bob 任选一个 $x$，$S'$ 的相邻两项都会相等，即 $S_i+T_{i+x}=S_{i+1}+T_{i+1+x}$，也就是说 $S_{i+1}-S_i=T_{i+x+1}-T_{i+x}$。既然 $x$ 是任意的，$i+x$ 也就可以任取，也就是说对任何 $i,j$ 都有 $S_{i+1}-S_i=T_{j+1}-T_j$。这样的话，不难看出所有的 $S_{i+1}-S_i$ 都相等，也就是说差分之后会全部相等。

我们发现，一步之内可以胜利当且仅当 $S_i$ 全都相等，即 $S$ 差分一次之后会变成全零序列；两次之后可以胜利当且仅当 $S$ 差分两次会变成全零序列。那么可不可以推广出这样的结论：$k$ 次之后可以胜利当且仅当 $S$ 差分 $k$ 次会变成全零序列？

答案是肯定的。如果 $S_i$ 差分 $k$ 次后会变成全 $0$，那么也就是说它差分 $k-1$ 次之后会变成每一项都相同的序列，设这个相同项为 $a$。我们取 $T_i=-S_i$，那么显然 $T$ 差分 $k-1$ 次就会变成每一项都是 $-a$ 的序列。那么无论 Bob 怎么移动这个 $T$ 再把它和 $S$ 加起来，得到的序列差分 $k-1$ 次之后都会变成全为 $a+(-a)=0$ 的序列。

这样我们就证明了“$S$ 差分 $k$ 次后会变成全 $0$ 序列”$\implies$“$k$ 步之后可以获胜”。另一个方向（从右边推到左边）也可以类似归纳证明，即若 $k$ 步后可以获胜那么 $S$ 差分 $k$ 次必须是全 $0$ 序列。

这样问题就转化成了：求最小的 $k$ 使得 $S$ 差分 $k$ 次后会变成全 $0$ 序列。为了统一说法，下面认为差分一次后 $S'_i=S_i-S_{i+1}$

为了下面方便，我们先说明一个事实：如果对 $S$ 差分 $p^k$ 次，那么得到的序列 $S'_i=S_i-S_{i+p^k}$。这是因为差分 $t$ 次后

代入 $t=p^k$ 后可以发现，对于 $0<j<p^k$，$\binom{p^k}{j}=\frac{p^k!}{j!(p^k-j)!}$ 里分子上 $p$ 的次数大于分母上 $j$ 的次数，因此 $\binom{p^k}{j}\equiv0\pmod p$。于是差分 $p_k$ 次后

（注意虽然 $p=2$ 时 $(-1)^{p^k}=1$，但是 $\bmod 2$ 意义下 $1=-1$）

那么考虑首先找到一个最小的 $k$，使得 $p^k$ 次差分后得到全 0，也就说对于任意的 $i$ 都有 $S_i=S_{i+p^k}$。但是这样的话又相当于 $S_i=S_{i+\gcd(p^k,n)}$（注意到下标都是 $\bmod n$ 意义下的，所以根据裴蜀定理存在 $ap^k+bn=\gcd(p^k,n)$，于是 $S_i=S_{i+ap^k}=S_{i+ap^k+bn}=S_{i+\gcd(p^k,n)}$）。

那么考虑如果 $n$ 中 $p$ 的次数是 $t$（即 $p^t|n,p^{t+1}\!\!\not|\,n$），则 $S_i=S_{i+p^k}(k>t)\implies S_i=S_{i+p^t}$。于是如果 $S$ 的 $p^t$ 阶差分不全为 $0$，则它的任意阶差分都不全为 $0$（否则如果存在 $a>p^t$ 阶差分全为 $0$，则找一个 $p^k\geq a$，那么显然 $p^k$ 阶差分也全为 $0$，因此 $p^t$ 阶差分为 $0$，与上面的假设矛盾）。

既然 $p^t$ 阶差分全为 $0$，这就说明 $S_i=S_{i+p^t}$。因此这个序列是一个周期为 $p^t$ 的序列，那么我们就可以只保留它的前 $p^t$ 项（因为它差分之后仍然是一个周期为 $p^t$ 的序列，相当于我们把周期为 $N$ 的一个环变成了周期为 $p^t$ 的一个环）。

假设答案为 $u$，那么如果 $u\leq p^{t-1}$（这可以扫一遍判断出来），则说明这个序列是一个周期为 $p^{t-1}$ 的序列，只保留它的前 $t-1$ 项之后递归处理即可；否则的话就把序列做一次 $p^{t-1}$ 阶差分继续处理。由于这个序列 $p^t$ 阶差分是 $0$，所以至多 $p$ 次之后就会递归。

复杂度则为

代码：

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>

typedef long long LL;

int read() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

const int N = 300050;

int A[N], B[N], n, p;

bool check(int q) {
  // A[i] == A[(i + q) % n]
  for (int i = 0; i < n; ++i)
    if (A[i] != A[(i + q) % n])
      return false;
  return true;
}

void modify(int q) {
  for (int i = 0; i < n; ++i)
    B[i] = (A[i] - A[(i + q) % n] + p) % p;
  memcpy(A, B, n * sizeof(int));
}

int main() {
  n = read(); p = read();
  for (int i = 0; i < n; ++i) A[i] = read() % p;
  int t = 1;
  while (n % (t * p) == 0) t *= p;
  if (!check(t)) {
    puts("-1");
    return 0;
  }
  int ans = 0;
  n = t;
  while (n > 1) {
    t = n / p;
    while (!check(t))
      modify(t), ans += t;
    n = t;
  }
  if (A[0] != 0) ++ans;
  printf("%d\n", ans);
}