CF2241G Summmon

注意，本题的答案可能无法用 int64 或 long long 表示，建议使用 int128。 对于长度为 $m$ 的任意数组 $b$，定义 $f(b)$ 为通过多次执行如下操作后能够达到的 $\max(b) - \min(b)$ 的最小可能值： - 任选一个下标 $1 \le i < m$，执行以下两种操作之一： 1. 令 $b_{i+1} := b_{i+1} + b_i$， 2. 令 $b_{i+1} := b_{i+1} - b_i$。 现给定长度为 $n$ 的数组 $a$，你的任务是计算所有 $a$ 的子数组 $^{*}$ 的 $f$ 值之和。更正式地，计算下式的值： $$ \sum_{1 \le l \le r \le n} f([a_l, a_{l+1}, \dots, a_r]) $$ $^{*}$ 数组 $b$ 是数组 $a$ 的子数组，当且仅当 $b$ 可以通过删除 $a$ 开头的若干元素（可以为零）和结尾的若干元素（可以为零），从 $a$ 得到。特别地，数组本身也是它的子数组。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）——表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

对于每个测试用例，输出一个整数——即 $\sum_{1 \le l \le r \le n} f([a_l, a_{l+1}, \dots, a_r])$ 的值。

对于第一个测试用例，考虑所有的子数组。 - 长度为 $1$ 的子数组 $[6]$、$[4]$ 和 $[8]$，无法进行任何操作，贡献均为 $0$。 - 对于 $[6,4]$，第一个元素固定为 $6$，第二个元素可以变为 $4+6=10$ 或 $4-6=-2$，此时数列的最大最小差值为 $4$ 或 $8$，但最优方式是不进行操作，贡献为 $2$。 - 对于 $[4,8]$，选择 $i=1$ 应用 $b_2 := b_2 - b_1$，则子数组变为 $[4, 4]$，其贡献为 $0$。 - 对于 $[6,4,8]$，保持前两个元素不变，选 $i=2$，对 $b_3 := b_3 - b_2$，$8$ 变为 $4$，此时数组为 $[6,4,4]$，此时 $\max(b)-\min(b)=6-4=2$，这是最优值。 因此，第一个测试用例的答案是 $0+0+0+2+0+2=4$。 对于第二个测试用例，所有长度为 $1$ 的子数组贡献 $0$。剩下的子数组中，只有 $[2,3]$、$[3,4]$ 和 $[2,3,4]$ 的贡献不为 $0$，每个贡献 $1$，因此答案为 $1+1+1=3$。 由 ChatGPT 5 翻译