Hello 2023 B. MKnez's ConstructiveForces Task

zsxuan / 2023-09-05 / 原文

构造一个数组 $a_1, a_2, \cdots, a_n$ 满足以下条件

$\forall i \in[1, n],\ a_i \neq 0$ 。
$\forall i \in [1, n - 1]， a_i + a_{i + 1} = \sum_{i = 1}^{n} a_i$ 。

显然从题中所给等式分析（加、减、乘、除、异或同理）：

诸如 $b_x = \sum_{i = 1}^n a_i - a_{x + y}$ 类，可化为 $\sum_{i = 1}^{n} b_i = k \sum_{i=1}^n a_i$ 。
诸如 $a_{x} + a_{x + y} = C$ 类，可化为

\[\begin{cases} a_x = a_{z}, \qquad &z \equiv x (\mod 2y) \\ a_{z} + a_{z + y} = C, \qquad &z \equiv x (\mod 2y) \end{cases} \]

其他递推式类或生成函数类

此题有

\[\begin{cases} a_1 = a_{x}, \qquad &x \equiv 1 (\mod 2) ① \\ a_{x} + a_{x + 1} = \sum_{i = 1}^n a_i, \qquad &x \equiv 1 (\mod 2) ② \end{cases} \]

根据 $①$ 可简单确定 $a$ 的形式为 $[u, v, u, v, u, v, \cdots]$ 。

当 $n$ 为偶数，显然地 $u$ 和 $v$ 的关系需要满足 $v = -u$ 。
当 $n$ 为奇数，$u + v = \sum_{i=1}^{n}a_i = \frac{n+1}{2}u + \frac{n-1}{2}v$ ，于是有 $\frac{n-1}{2}u + \frac{n-3}{2}v = 0$ 。于是可以得到 $u$ 和 $v$ 的关系为 $v = -\frac{n-1}{n-3}u$ 。$n = {1, 3}$ 时，$u, v$ 可以为 $0$ ，不满足题意。于是有 $n \geq 5, 2 \nmid n$ 。

当 $n$ 为偶数，不妨让 $u = 1$ 即可构造一个 $a$ 。否则不妨让 $u = n - 3, v = 1 - n$ 。

#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	if (n & 1 && n < 5) { std::cout << "NO" << '\n'; return; }
	std::cout << "YES" << '\n';
	if (~n & 1) for (int i = 1, sgn = 1; i <= n; i++, sgn *= -1)  std::cout << sgn << " \n"[i==n];
	else for (int i = 1; i <= n; i++) std::cout << (i&1?n-3:1-n) << " \n"[i==n];
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}