喵~ 大家好呀！我是你们的猫娘小助手，今天也要元气满满地帮大家解决问题哦！这次我们要看的题目是 Vupsen 和 Pupsen 的小故事，感觉会很有趣呢，一起来看看吧！

题目大意

Vupsen 和 Pupsen 得到一个整数数组。Vupsen 不喜欢数字 0，所以他把数组里所有的 0 都扔掉了，得到了一个长度为 n 的新数组 a。

Pupsen 呢，恰恰相反，他很喜欢 0。看到没有 0 的数组他就不开心了。为了哄 Pupsen 开心，Vupsen 决定创造一个新数组 b，长度也是 n，并且要满足以下条件：

1. a 和 b 的点积为 0，也就是 a₁*b₁ + a₂*b₂ + ... + aₙ*bₙ = 0。
2. b 数组里也不能有 0。
3. b 数组里的数不能太大，所有元素的绝对值之和 |b₁| + |b₂| + ... + |bₙ| 不能超过 10⁹。

题目保证一定能找到这样的数组 b，我们要做的就是帮 Vupsen 找到任何一个满足条件的 b 就可以啦，喵~

题解方法

这个问题呀，其实有个很巧妙的思路，就像猫猫把毛线球两两配对一样，喵~ 核心思想就是通过构造，让 aᵢ * bᵢ 的和两两或三三成组地抵消掉。我们可以分两种情况来讨论。

情况一：当 n 是偶数时

当 n 是偶数的时候，事情就变得超级简单了！我们可以把 a 数组的元素两个两个地分组：(a₁, a₂), (a₃, a₄), ... , (aₙ₋₁, aₙ)。

对于每一对 (aᵢ, aᵢ₊₁)，我们想让 aᵢ * bᵢ + aᵢ₊₁ * bᵢ₊₁ = 0。一个非常简单的构造方法就是： 令 bᵢ = -aᵢ₊₁ 令 bᵢ₊₁ = aᵢ

这样一来，aᵢ * bᵢ + aᵢ₊₁ * bᵢ₊₁ 就等于 aᵢ * (-aᵢ₊₁) + aᵢ₊₁ * aᵢ，结果正好是 0 啦！

因为题目保证了 a 数组里的元素都不是 0，所以我们构造出来的 bᵢ 和 bᵢ₊₁ 也肯定不是 0。每一对的和都是 0，那所有项加起来的总和当然也是 0 啦，嘻嘻~

情况二：当 n 是奇数时

那如果 n 是奇数怎么办呢？喵呜... 稍微麻烦一点点，但也不难！

奇数 n 减去 3 之后就是一个偶数了。所以我们可以先把前面 n-3 个元素像偶数情况那样，两两配对处理掉。这样一来，前面 n-3 项的点积之和就是 0 了。

现在，我们只需要处理最后剩下的三个孤零零的小朋友：aₙ₋₂, aₙ₋₁, aₙ。我们的目标是找到 bₙ₋₂, bₙ₋₁, bₙ，使得 aₙ₋₂*bₙ₋₂ + aₙ₋₁*bₙ₋₁ + aₙ*bₙ = 0。

这里同样可以用构造法。为了方便，我们把这三个数记作 aᵢ, aⱼ, aₖ。 我们可以尝试这样构造： 令 bᵢ = -(aⱼ + aₖ) 令 bⱼ = aᵢ 令 bₖ = aᵢ

代入验算一下：aᵢ * (-(aⱼ + aₖ)) + aⱼ * aᵢ + aₖ * aᵢ = -aᵢaⱼ - aᵢaₖ + aⱼaᵢ + aₖaᵢ = 0。 看，又成功抵消啦！

但是！我们得保证 b 里面没有 0。bⱼ 和 bₖ 等于 aᵢ，因为 aᵢ 不为 0，所以它们也不为 0。唯一可能出问题的是 bᵢ = -(aⱼ + aₖ)，万一 aⱼ + aₖ 等于 0 怎么办呀？

别担心！如果 aⱼ + aₖ 恰好是 0，我们可以换个组合嘛！比如，我们可以令 bᵢ = aⱼ, bⱼ = -(aᵢ+aₖ), bₖ = aⱼ。题目保证了 a 中任意三个数 aᵢ, aⱼ, aₖ，aᵢ+aⱼ, aᵢ+aₖ, aⱼ+aₖ 这三个和中至少有一个不为 0。所以我们只要检查一下，找到那个不为 0 的和，用它来构造我们的 b 就好啦~

例如，代码中的实现就是这样： 如果 aᵢ + aⱼ ≠ 0，就令 bᵢ = -aₖ, bⱼ = -aₖ, bₖ = aᵢ + aⱼ。 这样 aᵢ*(-aₖ) + aⱼ*(-aₖ) + aₖ*(aᵢ + aⱼ) = 0，并且 bₖ 不为 0。

最后，关于 |b| 的总和限制，由于 |aᵢ| ≤ 10⁴，我们构造出的 bᵢ 的绝对值最大也就是两个 aᵢ 的和，大约在 2*10⁴ 的级别。n 最大是 10⁵，总和 ∑|bᵢ| 大约是 n * |a| 的数量级，10⁵ * 10⁴ = 10⁹，完全在限制范围内，所以不用担心哦！

题解

下面就是这份思路的 C++ 代码实现啦，我已经帮你加上了一些可爱的注释哦~

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    std::vector<int> b(n);

    // 喵~ 如果 n 是偶数，就两两配对处理
    if (n % 2 == 0) {
        for (int i = 0; i < n; i += 2) {
            b[i] = -a[i + 1];
            b[i + 1] = a[i];
        }
    } else {
        // 如果 n 是奇数，先把前面 n-3 个配对
        for (int i = 0; i < n - 3; i += 2) {
            b[i] = -a[i + 1];
            b[i + 1] = a[i];
        }

        // 然后单独处理最后剩下的三个小可怜~
        int i = n - 3;
        int j = n - 2;
        int k = n - 1;

        // 找到一组和不为 0 的 a[x] + a[y] 来构造 b
        if (a[i] + a[j] != 0) {
            b[i] = -a[k];
            b[j] = -a[k];
            b[k] = a[i] + a[j];
        } else if (a[i] + a[k] != 0) {
            b[i] = -a[j];
            b[k] = -a[j];
            b[j] = a[i] + a[k];
        } else { // 题目保证 a[j] + a[k] != 0
            b[j] = -a[i];
            b[k] = -a[i];
            b[i] = a[j] + a[k];
        }
    }

    // 输出我们找到的 b 数组
    for (int i = 0; i < n; ++i) {
        std::cout << b[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题主要考察的是 构造性算法 (Constructive Algorithm) 的思想。

构造性算法 不像是搜索或者动态规划那样去寻找一个已经存在的最优解，而是根据题目给出的条件和约束，直接按照一套精心设计的规则来“构造”出一个符合所有要求的解。这类问题的特点是解不唯一，我们只需要找到任意一个即可。

在本题中，我们利用了线性代数中一个非常基础的性质：对于方程 ax + by = 0，一组非零解可以是 x = -b, y = a。我们将这个思想扩展到了 n 个变量，通过两两配对或三三成组的方式，将一个大问题分解成了很多个这样的小问题来解决。

这种“分解-构造”的思维方式在算法竞赛中非常有用，当你遇到要求“找到一个满足某某条件的方案”时，不妨想一想是否能用简单的规则直接构造出答案来，而不是陷入复杂的搜索中哦！

好啦，今天的讲解就到这里啦！希望我的讲解能帮到你，喵~ 如果还有问题，随时可以再来找我玩哦！