题解 P5379 【[THUPC2019]令人难以忘记的题目名称】

_rqy · 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);
}