CF2241G - Summmon

题目描述

对任意长度为 $m$ 的数组 $b$，定义 $f(b)$ 为通过若干次操作后，能够得到的 $\max(b)-\min(b)$ 的最小值。

一次操作为：选择一个下标 $i$，满足 $1\le i<m$，然后执行以下两种操作之一：

• 令 $b_{i+1}:=b_{i+1}+b_i$；
• 令 $b_{i+1}:=b_{i+1}-b_i$。

给定一个长度为 $n$ 的数组 $a$，请计算所有连续子数组的 $f$ 值之和，即：

$$\sum_{1\le l\le r\le n} f([a_l,a_{l+1},\ldots,a_r])。$$

本题包含多组测试数据。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出一行一个整数，表示所有连续子数组的 $f$ 值之和。

注意答案可能超过 64 位有符号整数范围。

样例输入 #1

5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6

样例输出 #1

4
3
39
72
111

数据范围

• $1\le T\le 10^4$；
• $1\le n\le 2\times 10^5$；
• $1\le a_i\le 10^9$；
• 单个测试点内所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

标签与难度

• 标签：数学，栈，数论，贡献
• 难度：Codeforces 约 2200