CF2275C.Unrequited Love
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 a1,a2,…,an units of audience love.
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≤x≤n−4) is the keys x, x+2, and x+4, which brings ax+ax+2−ax+4 units of audience love.
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.
Count the number of ways to choose two such triads.
K1o0n 已经到达了这样一个阶段:为了获得完全的幸福,他唯一缺少的是一样乐器,于是他买了一台二手合成器。该乐器有 n 个琴键,分别带来 a1,a2,…,an 单位的观众喜爱值。
一次只弹奏一个音符很无聊,因此 K1o0n 学会了一种技巧——三和弦(triad):同时按下三个琴键,其中每对琴键之间恰好间隔一个琴键。起始于位置 x(1≤x≤n−4)的三和弦由琴键 x、x+2 和 x+4 组成,带来的观众喜爱值为 ax+ax+2−ax+4。
这些琴键已经老旧,每个琴键恰好只能被按压一次。因此,K1o0n 想要恰好选择两个互不共享任何琴键的不同三和弦。此外,他还希望这两个三和弦带来的观众喜爱值完全相同。
请计算满足上述条件的三和弦对的选择方案数。
输入格式
The first line contains an integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains an integer n (6≤n≤2⋅105) — the number of keys.
The second line of each testcase contains n integers ai (−104≤ai≤104) — the units of audience love.
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)—— 表示测试用例的数量。
每个测试用例的第一行包含一个整数 n(6≤n≤2⋅105)—— 表示按键的数量。
每个测试用例的第二行包含 n 个整数 ai(−104≤ai≤104)—— 表示观众喜爱度的单位值。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each testcase, output one integer — the number of unordered pairs of disjoint triads with equal audience love values.
Note that the answer may not fit into a 32-bit type. Use a 64-bit type (long long in C++, long in Java).
对于每个测试用例,输出一个整数——满足观众喜爱值相等且互不相交的无序三元组对的数量。
注意:答案可能无法用 32 位类型存储,请使用 64 位类型(C++ 中为 long long,Java 中为 long)。
输入输出样例
输入#1
3 6 5 1 4 2 2 -4 7 0 0 0 0 0 0 0 12 -4 3 0 -4 -4 -1 -4 1 -3 -2 -2 -1
输出#1
1 2 5
说明/提示
In the first testcase, such a pair is unique: x=1, y=2: 5+4−2=1+2−(−4).
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.
在第一个测试用例中,满足条件的数对是唯一的:x=1,y=2:5+4−2=1+2−(−4)。
在第二个测试用例中,存在两个满足条件的数对:x=1,y=2 和 x=3,y=2,且每个三元组带来的观众喜爱度均为 0 单位。
输入解题思路,AI测评打分。不知道怎么写?