A16718. Absolute Cinema
编程题
普及/提高-
知识点
题目描述
现在有一个由 $n$ 个整数（$n \ge 2$）组成的隐藏序列 $a_1, a_2, \ldots, a_n$。保证对于所有 $1 \le i \le n$，都有 $|a_i| \le 1000$。
定义函数 $f(x)$ 如下：
$$ f(x) = \sum_{i=1}^n a_i \cdot |i-x| $$
给定 $f(1), f(2), \ldots, f(n)$ 共 $n$ 个值，请你求出 $a_1, a_2, \ldots, a_n$ 的具体值。
保证 $a_1, a_2, \ldots, a_n$ 的值能够被唯一确定。
定义函数 $f(x)$ 如下：
$$ f(x) = \sum_{i=1}^n a_i \cdot |i-x| $$
给定 $f(1), f(2), \ldots, f(n)$ 共 $n$ 个值，请你求出 $a_1, a_2, \ldots, a_n$ 的具体值。
保证 $a_1, a_2, \ldots, a_n$ 的值能够被唯一确定。
输入格式
每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。接下来是 $t$ 组测试用例。
每组测试用例的第一行包含一个整数 $n$（$\color{red}{2} \le n \le 300\,000$）。
第二行包含 $n$ 个整数 $f(1), f(2), \ldots, f(n)$（$-10^{14} \le f(i) \le 10^{14}$）。
保证所有测试用例中 $n$ 的总和不超过 $300\,000$。
每组测试用例的第一行包含一个整数 $n$（$\color{red}{2} \le n \le 300\,000$）。
第二行包含 $n$ 个整数 $f(1), f(2), \ldots, f(n)$（$-10^{14} \le f(i) \le 10^{14}$）。
保证所有测试用例中 $n$ 的总和不超过 $300\,000$。
输出格式
对于每组测试用例，输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$，每组输出占一行（保证 $|a_i| \le 1000$）。
保证 $a_1, a_2, \ldots, a_n$ 的值能够被唯一确定。
保证 $a_1, a_2, \ldots, a_n$ 的值能够被唯一确定。
输入输出样例
输入 #1
4 4 17 9 9 13 6 -37 -32 -15 4 27 42 5 -26 -32 -24 -4 2 2 420 -69
输出 #1
1 4 2 3 3 6 1 2 -4 -7 -6 7 6 -7 -6 -69 420
说明/提示
在第一个测试用例中，隐藏序列为 $a=[1,4,2,3]$。
各 $f(1), f(2), \ldots, f(n)$ 为：
- $f(1) = 1 \cdot |1-1| + 4 \cdot |2-1| + 2 \cdot |3-1| + 3 \cdot |4-1| = 0+4+4+9 = 17$；
- $f(2) = 1 \cdot |1-2| + 4 \cdot |2-2| + 2 \cdot |3-2| + 3 \cdot |4-2| = 1+0+2+6 = 9$；
- $f(3) = 1 \cdot |1-3| + 4 \cdot |2-3| + 2 \cdot |3-3| + 3 \cdot |4-3| = 2+4+0+3 = 9$；
- $f(4) = 1 \cdot |1-4| + 4 \cdot |2-4| + 2 \cdot |3-4| + 3 \cdot |4-4| = 3+8+2+0 = 13$。
各 $f(1), f(2), \ldots, f(n)$ 为：
- $f(1) = 1 \cdot |1-1| + 4 \cdot |2-1| + 2 \cdot |3-1| + 3 \cdot |4-1| = 0+4+4+9 = 17$；
- $f(2) = 1 \cdot |1-2| + 4 \cdot |2-2| + 2 \cdot |3-2| + 3 \cdot |4-2| = 1+0+2+6 = 9$；
- $f(3) = 1 \cdot |1-3| + 4 \cdot |2-3| + 2 \cdot |3-3| + 3 \cdot |4-3| = 2+4+0+3 = 9$；
- $f(4) = 1 \cdot |1-4| + 4 \cdot |2-4| + 2 \cdot |3-4| + 3 \cdot |4-4| = 3+8+2+0 = 13$。