2275C.md (2010B)
1 Source: https://codeforces.com/problemset/problem/2275/C 2 3 C. Unrequited Love 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 K1o0n reached the stage where, for complete happiness, he only lacked a musical instrument, and bought a synthesizer second-hand. The instrument has $n$ keys, giving $a_1, a_2, \ldots, a_n$ units of audience love. 22 23 Playing one note at a time is boring, so K1o0n learned a single technique — a triad: three keys with one key between each pair, pressed simultaneously. A triad starting at $x$ ($1 \le x \le n - 4$) is the keys $x$, $x+2$, and $x+4$, which brings $a_x + a_{x+2} - a_{x+4}$ units of audience love. 24 25 The keys are old, and each can withstand exactly one press. Therefore, K1o0n wants to choose exactly two different triads that do not share any keys. In addition, he wants both triads to bring the same amount of audience love. 26 27 Count the number of ways to choose two such triads. 28 29 Input 30 31 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 32 33 The first line of each testcase contains an integer $n$ ($6 \le n \le 2 \cdot 10^5$) — the number of keys. 34 35 The second line of each testcase contains $n$ integers $a_i$ ($-10^4 \le a_i \le 10^4$) — the units of audience love. 36 37 It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each testcase, output one integer — the number of unordered pairs of disjoint triads with equal audience love values. 42 43 Note that the answer may not fit into a 32-bit type. Use a 64-bit type (long long in C++, long in Java). 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 6 53 54 5 1 4 2 2 -4 55 56 7 57 58 0 0 0 0 0 0 0 59 60 12 61 62 -4 3 0 -4 -4 -1 -4 1 -3 -2 -2 -1 63 ``` 64 65 Output 66 67 ``` 68 1 69 70 2 71 72 5 73 ``` 74 75 Note 76 77 In the first testcase, such a pair is unique: $x = 1$, $y = 2$: $5 + 4 - 2 = 1 + 2 - (-4)$. 78 79 In the second testcase, there are two such pairs: $x = 1$, $y = 2$ and $x = 3$, $y = 2$, and each triad brings $0$ units of audience love.