自动搬运

查看原文

来自洛谷，原作者为

	Stinger **

搬运于2025-08-24 22:19:50，当前版本为作者最后更新于2021-01-28 17:08:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题面出奇的友好，就是构造一个序列 $a$ 使得（$b_i$表示目标环）：

$$\begin{cases} a_n+a_1+a_2=b_1\\ a_1+a_2+a_3=b_2\\ a_2+a_3+a_4=b_3\\ ...\\ a_{n-1}+a_n+a_1=b_n \end{cases} $$

做差可得：

$$\begin{cases} a_n-a_3=b_1-b_2\\ a_1-a_4=b_2-b_3\\ a_2-a_5=b_3-b_4\\ a_{n-1}-a_2=b_{n-1}-b_n\\ \end{cases} $$

移项可得：

$$\begin{cases} a_3=b_2-b_1+a_n\\ a_4=b_3-b_2+a_1\\ a_5=b_4-b_3+a_2\\ a_n=b_{n-1}-b_{n-2}+a_{n-3}\\ \end{cases} $$

因此可得：

$$a_i=a_{i-3}+b_{i-1}+b_{i-2}$$ $$a_{i+3}=a_i+b_{i+2}-b_{i+1}$$

其中加法得到的下标要取模什么的都知道，比如说 $i=5,n=6$，$i+3$ 在程序实现里应为 $2$。

将第一个方程组全部相加即得：

$$\sum\limits^{i\le n}_{i=1}a_i=\sum\limits^{i\le n}_{i=1}b_i\div 3 $$

分两种情况：

1. $n\equiv 1 \operatorname{mod} 3$

那么这要求我们知道 $a_1,a_2,a_3$ 的值。随便给 $a_1,a_2,a_3$ 乱设一个值（我设为 $0$）。然后根据 $a_1,a_2,a_3$ 的值推出 $a$ 数组的值。然后调整一下 $a$ 序列的值，对于一个满足 $i\equiv 1 \operatorname{mod} 3$ 的 $a_i$，将这个数减去 $(\sum\limits^{i\le n}_{i=1}b_i-\sum\limits^{i\le n}_{i=1}a_i\times 3)\div n$，这样能使得总和满足上面得出的关于 $a$ 数组的综合的式子。

2. 除（1）以外的情况。

这种情况把 $a_1$ 乱设一个值就能推出整个 $a$ 数组。那么将每个 $a_i$ 减去 $(\sum\limits^{i\le n}_{i=1}b_i-\sum\limits^{i\le n}_{i=1}a_i\times 3)\div n\div 3$。

以上涉及到的所有除法，若不能整除，则无解。

$Code:$

#include <cstdio>
#define int long long

int a[10005], b[10005], n;
bool mark[10005];
inline int Nxt(const int p, const int x) {
	return p + x == n ? n : (p + x) % n;
}
inline void work(const int x) {
	int i(x);
	mark[x] = true;
	while (true) {
		if (mark[Nxt(i, 3)]) break;
		a[Nxt(i, 3)] = a[i] + b[Nxt(i, 2)] - b[Nxt(i, 1)];
		mark[Nxt(i, 3)] = true;
		i = Nxt(i, 3);
	}
}

signed main() {
	scanf("%lld", &n);
	for (int i(1); i <= n; ++ i) scanf("%lld", b + i);
	if (n % 3 == 0) {
		int sum(0), sum2(0), t(0);
		work(1); work(2); work(3);
		for (int i(1); i <= n; ++ i) sum += a[i], sum2 += b[i];
		t = (sum2 - sum * 3) / n;
		for (int i(1); i <= n; ++ i) printf("%lld\n", i % 3 == 1 ? a[i] + t : a[i]);
	}
	else {
		int sum(0), sum2(0), t(0);
		work(1);
		for (int i(1); i <= n; ++ i) sum += a[i], sum2 += b[i];
		t = (sum2 - sum * 3) / 3 / n;
		for (int i(1); i <= n; ++ i) printf("%lld\n", a[i] + t);
	}
	return 0;
}