不是很懂为啥这题有 2300.jpg
首先显然在经过一次操作后 \(\displaystyle\sum_{i=1}^na_i\) 不变，所以有解的充分条件为 \(\displaystyle\sum_{i=1}^na_i=0\)。
我们设 \(x_i\) 表示我们对下标 \(i\) 进行了 \(x_i\) 次这样的操作，那么我们有一系列方程，其中每个方程都形如 \(a_i-x_{i-1}-x_{i+1}+2x_i=0\)。考虑通过 \(x_1,x_2\) 推出后续的数，我们有：
于是可以得到：
定理 1：对所有 \(i\ge 2\)，\(x_i\) 必定可以表示为 \(v_i-(i-2)x_1+(i-1)x_2\) 的形式，且 \(v_i=a_{i-1}-v_{i-2}+2v_{i-1}\)。
证明：
考虑归纳。我们在上面列出的方程中已经证明了对 \(i=2,3\) 来说定理 1 成立，对 \(i\ge 4\)，我们有：
故得证。
考虑 \(x_{n+1}\)，我们知道它等于 \(v_{n+1}-(n-1)x_1+nx_2\)，但同时由于 \(a_i\) 的循环性，它也等于 \(x_1\)。于是有 \(x_1-x_2=\dfrac{v_{n+1}}{n}\)，因为 \(x_1,x_2\) 都为整数，所以有解的充要条件是 \(n\mid v_{n+1}\)。以下设 \(d=\dfrac{v_{n+1}}{n}=x_1-x_2\)。
那么我们可以使用 \(x_1\) 和 \(d\) 得出剩下所有 \(x_i\)。具体的，我们有：
因为我们要求 \(x_i\ge 0\) 的同时使得 \(\displaystyle\sum_{i=1}^nx_i\) 的值最小，且 \(x_i\) 都为 \(x_1\) 加上一个数，所以我们需要让 \(x_1\) 最小，因此有：
注意到 \(x_1\ge 0\)，所以最后 \(x_1\) 还要和 \(0\) 取 \(\max\)。然后直接算出剩下的 \(x_i\)，累加答案即可。
#include <numeric>
#include <iostream>
using namespace std;
using LL = long long;
const int kN = 2e5 + 2;
int n, a[kN];
LL v[kN], x1, ans;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
if (accumulate(a + 1, a + n + 1, 0) != 0) {
cout << "-1";
return 0;
}
for (int i = 3; i <= n + 1; ++i) {
v[i] = a[i - 1] - v[i - 2] + 2 * v[i - 1];
}
if (v[n + 1] % n != 0) {
cout << "-1";
return 0;
}
LL d = v[n + 1] / n;
for (int i = 2; i <= n; ++i) {
x1 = max(x1, (i - 1) * d - v[i]);
}
for (int i = 1; i <= n; ++i) {
ans += x1 - (i - 1) * d + v[i];
}
cout << ans;
return 0;
}