哈喵~！各位同学，今天我们要一起解决的是 Codeforces 上的 2117D - Retaliation 这道题哦。这道题看起来有点吓人，但只要我们把它变成熟悉的数学问题，就会变得像是在玩毛线球一样简单啦，嘿嘿~

下面就让本猫娘带你一步步拆解这道题吧！

题目大意

题目给了我们一个有 n 个整数的数组 a，我们的目标是把数组里所有的元素都变成 0，也就是“引爆”这个数组，喵~

我们可以进行两种操作，次数不限：

1. 操作一：对于数组里所有的下标 i（从 1 开始哦），都把 a_i 减去 i。
2. 操作二：对于数组里所有的下标 i（从 1 开始哦），都把 a_i 减去 n - i + 1。

问题就是：我们能不能通过任意次的操作一和操作二，把数组 a 的所有元素都变成 0 呢？如果可以，就输出 "YES"，不然就输出 "NO"，喵。

解题思路

一看到这种“进行若干次操作，问能否达到某个状态”的问题，我们的第一反应通常是建立数学模型，喵~

让我们来设定一下变量：

• 假设我们进行了 x 次操作一。
• 假设我们进行了 y 次操作二。

因为操作次数不能是负数，所以 x 和 y 都必须是 非负整数（x >= 0, y >= 0）。

现在，我们来看看对于数组中的第 i 个元素 a_i，它最终要变成 0，意味着它被减去的总数必须等于它原来的值。 经过 x 次操作一，a_i 会被减去 x * i。 经过 y 次操作二，a_i 会被减去 y * (n - i + 1)。

所以，为了让 a_i 变成 0，必须满足下面的等式： a_i = x * i + y * (n - i + 1)

这个等式必须对所有的 i (从 1 到 n) 都成立。

我们来整理一下这个式子，看看能不能发现什么小秘密，喵~ a_i = x*i + y*n - y*i + ya_i = (x - y) * i + y * (n + 1)

嗯~？各位同学有没有觉得这个式子很眼熟呀？如果把 a_i 看作是 Y，把 i 看作是 X，那这不就是一个标准的**一次函数（直线方程）**嘛！ Y = mX + c 其中，斜率 m = x - y，截距 c = y * (n + 1)。

这意味着，如果我们把 (i, a_i) 这些点画在二维坐标系里，它们必须全都在同一条直线上！我们把这个性质叫做共线性（Collinearity）。

所以，解题的思路就清晰了喵：

1. 检查共线性：首先，我们要判断所有的点 (i, a_i) 是不是在一条直线上。
2. 求解 x 和 y：如果它们确实在一条直线上，我们就需要去解出对应的 x 和 y，并且检查它们是不是非负整数。

如果两个条件都满足，答案就是 "YES"，否则就是 "NO"。

题解详解

接下来，我们把思路变成具体的步骤和代码，喵~ 为了和 C++ 代码的习惯保持一致，我们接下来的讨论使用 0-based 索引，也就是下标从 0 到 n-1。此时，原来的 i 变成了 k+1。

原公式 a_i = x*i + y*(n-i+1) 变为： a[k] = x * (k + 1) + y * (n - k) （其中 k = 0, 1, ..., n-1）

第一步：检查共线性喵

要判断 n 个点 (k, a[k]) 是否共线，最简单的方法就是看任意两点之间的斜率是否都相等。 我们可以选定两个基准点，比如第一个点 (0, a[0]) 和最后一个点 (n-1, a[n-1])。它们确定的斜率是： slope = (a[n-1] - a[0]) / (n-1 - 0)

然后我们检查其他所有的点 (k, a[k]) (其中 k = 1, ..., n-2) 和第一个点 (0, a[0]) 构成的斜率是不是也等于这个 slope。 (a[k] - a[0]) / (k - 0) == (a[n-1] - a[0]) / (n-1)

为了避免使用浮点数除法可能带来的精度问题，我们使用交叉相乘来判断，这样就只用整数运算啦，更安全喵！ (a[k] - a[0]) * (n - 1) == (a[n-1] - a[0]) * k

我们只需要写一个循环，从 k=1 到 n-2，检查这个等式是否对所有 k 都成立。如果有一个不成立，那它们就不共线，直接输出 "NO" 就可以啦。

特殊情况：当 n=2 时，只有两个点，两个点必然共线，所以不需要进行这个检查。

第二步：求解 x 和 y 喵

如果所有点都共线，我们就来求解 x 和 y。我们只需要两个方程就能解出两个未知数。我们就用 k=0 和 k=n-1 的情况来建立方程组：

1. 当 k=0 时: a[0] = x * (0 + 1) + y * (n - 0) => a[0] = x + n*y
2. 当 k=n-1 时: a[n-1] = x * (n-1 + 1) + y * (n - (n-1)) => a[n-1] = n*x + y

这是一个简单的二元一次方程组：

x + n*y = a[0]
n*x + y = a[n-1]

解这个方程组，可以得到（推导过程可以自己试试看哦，很有趣的喵~）： x = (n * a[n-1] - a[0]) / (n^2 - 1)y = (n * a[0] - a[n-1]) / (n^2 - 1)

第三步：验证解的有效性喵

我们已经得到了 x 和 y 的表达式，现在需要验证它们是否是非负整数。

• 非负：分母 n^2 - 1 因为 n >= 2 肯定是正数，所以我们只需要保证分子非负。
  • n * a[n-1] - a[0] >= 0
  • n * a[0] - a[n-1] >= 0
• 整数：分母必须能整除分子。
  • (n * a[n-1] - a[0]) % (n^2 - 1) == 0
  • (n * a[0] - a[n-1]) % (n^2 - 1) == 0

如果这四个条件全部满足，那么就存在合法的 x 和 y，答案是 "YES"！否则，就是 "NO"。

代码实现

下面是完整的 C++ 代码，加上了本猫娘的注释，帮助你理解每一部分的作用喵~

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n); // a_i可能很大，要用 long long 喵
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 对于 n <= 2 的情况, 任意两个点都是共线的, 直接跳过检查
    // 我们的循环条件 k < n-1 天然处理了这种情况
    bool collinear = true;
    if (n > 2) { // 只有 n > 2 时才需要检查超过两个点是否共线
        for (int k = 1; k < n - 1; ++k) {
            // 使用交叉相乘避免除法精度问题
            // (a[k] - a[0]) / k == (a[n-1] - a[0]) / (n-1)
            // 注意 n 和 k 都是 int, 但 a[i] 是 long long,
            // 为了防止溢出, 乘法要转成 long long
            long long lhs = (a[k] - a[0]) * (long long)(n - 1);
            long long rhs = (a[n - 1] - a[0]) * (long long)k;
            if (lhs != rhs) {
                collinear = false;
                break;
            }
        }
    }

    if (!collinear) {
        std::cout << "NO\n";
        return;
    }

    // 如果共线, 就求解 x 和 y
    // x = (n*a[n-1] - a[0]) / (n^2 - 1)
    // y = (n*a[0] - a[n-1]) / (n^2 - 1)
    long long denom = (long long)n * n - 1;
    long long num_x = (long long)n * a[n - 1] - a[0];
    long long num_y = (long long)n * a[0] - a[n - 1];

    // 检查 x 和 y 是否为非负整数
    if (num_x >= 0 && num_y >= 0 && num_x % denom == 0 && num_y % denom == 0) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题主要用到了两个基础的数学知识点，喵~

1. 线性方程组 (System of Linear Equations) 当我们有两个或更多的未知数，并且有同样数量的线性方程时，我们就可以尝试解出这些未知数。这道题里，我们通过 k=0 和 k=n-1 的情况建立了关于 x 和 y 的二元一次方程组，并成功解出了它们。这是代数中最基本也最有用的工具之一。

2. 共线性 (Collinearity) 如果三个或更多的点位于同一直线上，我们就说这些点是共线的。在二维平面上，判断共线的常用方法是斜率法。即，任取两点计算斜率，如果所有点对计算出的斜率都相等，那么这些点就是共线的。为了避免计算机处理浮点数时可能出现的误差，我们常常使用交叉相乘把除法变成整数乘法来判断，这是一个非常实用的小技巧哦！

好啦，这道题的讲解就到这里啦！是不是感觉把问题转换成数学模型后，一切都变得清晰起来了呢？希望这篇题解能帮到你喵~ 下次再见啦！(ฅ'ω'ฅ)