CF2029I.Variance Challenge

Kevin 最近学会了方差的定义。对于一个长度为 $n$ 的数组 $a$，其方差定义如下：

• 令 $x = \dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i$，即 $x$ 是数组 $a$ 的平均值；
• 那么，$a$ 的方差为 $V(a) = \frac{1}{n}\sum_{i=1}^n (a_i - x)^2$。

现在，Kevin 给你一个由 $n$ 个整数构成的数组 $a$，以及一个整数 $k$。你可以对 $a$ 执行如下操作：

• 选择一个区间 $[l, r]$（$1 \le l \le r \le n$），然后对于每个 $l \le i \le r$，将 $a_i$ 增加 $k$。

对于每个 $1 \le p \le m$，你需要分别独立地求出恰好执行 $p$ 次操作后，数组 $a$ 的最小可能方差。

为简化问题，你只需要输出答案乘以 $n^2$ 的结果。可以保证结果总是整数。

每个测试包含多组测试用例。输入的第一行为一个整数 $t$（$1 \le t \le 100$）——表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行为三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 5000$，$\color{red}{n \cdot m \le 2 \cdot 10^4}$，$1 \le k \le 10^5$）——数组 $a$ 的长度、最多操作次数以及每次增加的数。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$）——数组 $a$ 的元素。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^4$。

对于每组测试用例，输出 $m$ 个整数，依次表示恰好执行 $p$ 次操作后数组 $a$ 的最小可能方差乘以 $n^2$ 的结果（$p = 1, 2, \ldots, m$）。

在第一个测试用例中：

• 对于 $p = 1$，你可以在区间 $[1, 1]$ 上操作，将 $a$ 从 $[1, 2, 2]$ 变为 $[2, 2, 2]$。此时所有元素都相等，方差为 $0$。
• 对于 $p = 2$，你可以依次在区间 $[1, 3]$ 和 $[1, 1]$ 上操作，将 $a$ 从 $[1, 2, 2]$ 变为 $[2, 3, 3]$，再变为 $[3, 3, 3]$。此时所有元素都相等，方差为 $0$。

在第二个测试用例中，一些可能的最优选择为：

• $p=1$：$[\underline{1,}\,2,2] \to [3,2,2]$；
• $p=2$：$[1,\underline{2,2}] \to [\underline{1,}\,4,4] \to [3,4,4]$。

在第三个测试用例中，一些可能的最优选择为：

• $p=1$：$[10,\underline{1,1,1,1,10,1,1,1,1}] \to [10,2,2,2,2,11,2,2,2,2]$；
• $p=2$：$[10,1,1,1,1,10,\underline{1,1,1,1}] \to [10,\underline{1,1,1,1},10,2,2,2,2] \to [10,2,2,2,2,10,2,2,2,2]$。

在第八个测试用例中，对于所有 $p$，最优选择都是每次对整个数组操作。

由 ChatGPT 4.1 翻译