2195D.md (1899B)
1 Source: https://codeforces.com/problemset/problem/2195/D 2 3 D. Absolute Cinema 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a hidden sequence $a_1,a_2,\ldots,a_n$ of $n$ integers ($n \ge 2$). It is guaranteed that $|a_i| \le 1000$ for all $1 \le i \le n$. 22 23 Let's define a function $f(x)$ as follows: 24 25 $$f(x)=\sum_{i=1}^n a_i \cdot |i-x|$$ 26 27 Given $n$ values $f(1),f(2),\ldots,f(n)$, please determine the values of $a_1,a_2,\ldots,a_n$. 28 29 It is guaranteed that the values $a_1,a_2,\ldots,a_n$ can be determined uniquely. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($\color{red}{2} \le n \le 300\,000$). 36 37 The second line of each test case contains $n$ integers $f(1),f(2),\ldots,f(n)$ ($-10^{14} \le f(i) \le 10^{14}$). 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$. 40 41 Output 42 43 For each test case, output $n$ integers $a_1,a_2,\ldots,a_n$ on a separate line ($|a_i| \le 1000$). 44 45 It is guaranteed that the values $a_1,a_2,\ldots,a_n$ can be determined uniquely. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 4 55 56 17 9 9 13 57 58 6 59 60 -37 -32 -15 4 27 42 61 62 5 63 64 -26 -32 -24 -4 2 65 66 2 67 68 420 -69 69 ``` 70 71 Output 72 73 ``` 74 1 4 2 3 75 76 3 6 1 2 -4 -7 77 78 -6 7 6 -7 -6 79 80 -69 420 81 ``` 82 83 Note 84 85 In the first test case, the hidden sequence is $a=[1,4,2,3]$. 86 87 The values $f(1),f(2),\ldots,f(n)$ are as follows: 88 89 * $f(1) = 1 \cdot |1-1| + 4 \cdot |2-1| + 2 \cdot |3-1| + 3 \cdot |4-1| = 0+4+4+9 = 17$; 90 * $f(2) = 1 \cdot |1-2| + 4 \cdot |2-2| + 2 \cdot |3-2| + 3 \cdot |4-2| = 1+0+2+6 = 9$; 91 * $f(3) = 1 \cdot |1-3| + 4 \cdot |2-3| + 2 \cdot |3-3| + 3 \cdot |4-3| = 2+4+0+3 = 9$; 92 * $f(4) = 1 \cdot |1-4| + 4 \cdot |2-4| + 2 \cdot |3-4| + 3 \cdot |4-4| = 3+8+2+0 = 13$.