← 返回题目列表

Codeforces · 2195/D

D. 绝对影院

中文机器翻译题面 查看原题

存在 $$$n$$$ 的隐藏序列 $$$a_1,a_2,\ldots,a_n$$$ 整数 ($$$n \ge 2$$$)。保证 $$$|a_i| \le 1000$$$ 对于所有 $$$1 \le i \le n$$$。

让我们定义一个函数 $$$f(x)$$$ 如下:

$$f(x)=\sum_{i=1}^n a_i \cdot |i-x|$$

给定 $$$n$$$ 值 $$$f(1),f(2),\ldots,f(n)$$$,请确定 $$$a_1,a_2,\ldots,a_n$$$ 的值。

保证值 $$$a_1,a_2,\ldots,a_n$$$ 可以唯一确定。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$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$$$ 可以唯一确定。

示例

输入
复制

4
4
17 9 9 13
6
-37 -32 -15 4 27 42
5
-26 -32 -24 -4 2
2
420 -69

输出
复制

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$$$。