题目描述

难度分:$2600$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^3$。

每组数据输入$n(1 \leq n \leq 2 \times 10^3)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。

你可以执行如下两类操作：

1. 合并相邻元素。例如把$[2,2,3]$的前两个数合并成$4$，得到$[4,3]$。
2. 把一个大于$1$的数$v$分解为两个正整数$x$和$y$，满足$x+y=v$。例如把$[2,2,3]$的第一个数分解为两个$1$，得到$[1,1,2,3]$。

定义$f(b)$表示把$b$变成回文数组的最少操作次数。对于$a$的所有非空连续子数组$b$，计算$f(b)$，输出所有$f(b)$之和。

输入样例

4
3
2 1 3
4
1 1 1 1
5
4 2 3 1 5
4
1 2 1 2

输出样例

3
0
14
5

算法

贡献法

思维难度很高的一道贡献计算题，很不好想。

合并操作，每次可以减少一个数字。

分解操作，比如最左边是$2$，最右边是$5$，我们分解大的那个数，得到$3$和$2$。这时候在两端的两个$2$就可以配对，把两边的$2$去掉，接下来考虑把中间部分变为回文。此时中间部分的最右端就是一个$3$，相比之前左边是$2$右边是$5$，这次操作就等价于去掉最左边的$2$，并修改最右边的$5$为$3$，所以每次操作也可以减少一个数字。

因此，这两种操作效果是等效的，不妨只考虑好理解的合并操作。

如果按照每次减少一个数的思路，那么长为$m$的子数组$b$操作$m−1$次可以变成一个数，此时一定是回文的。

接下来我们减少操作次数，比如$b=[2,2,1,3]$，左右都可以合并成$4$，最后得到$[4,4]$，这样只需操作$2$次而不是$3$次，减少了$1$次操作。

又比如$b=[2,2,9,1,3]$，左右都可以合并成$4$，最后得到$[4,9,4]$，这样只需操作$2$次而不是$4$次，减少了$2$次操作。

考虑一般情况，发现如果前缀$[0,i]$与后缀$[j,m−1]$的元素和相同，那么可以减少$1$次操作。注意前后缀可以相交，在$b=[2,2,9,1,3]$这个例子中，我们有$2+2=1+3$，同时还有$2+2+9=9+1+3$，所以可以减少$2$次操作（有多少个相同的和就可以减少几次操作，看上去好像是这个规律）。

这时候就可以考虑贡献法，如果有两个非空子数组$[i_1,j_1],[i_2,j_2]$的元素和相同，那么对于下标从$i_1$到$j_2$的子数组$b$来说，可以减少$1$次操作，对答案的贡献就是$−1$。

所以只需统计非空子数组和的个数$cnt\_s$。遍历到子数组$[i,j]$时，设其元素和为$s$，那么它与之前统计过的$cnt\_s$个子数组和相同，对答案的贡献就是$j−i−cnt\_s$。其中$j−i$是不考虑相同前后缀时，长为$j−i+1$的子数组所需的操作次数（即一次减少一个数的合并操作）。

复杂度分析

时间复杂度

双重循环遍历每个子数组$[i,j]$就能计算出答案，时间复杂度为$O(n^2)$。

空间复杂度

空间消耗主要在于哈希表$counter$，最差情况下每个子数组$[i,j]$都有不同的累加和，这样就会存$O(n^2)$级别的键值对。因此，额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2010;
int T, n, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        LL ans = 0;
        unordered_map<int, int, custom_hash> counter;
        for(int i = 1; i <= n; i++) {
            int s = 0;
            for(int j = i; j <= n; j++) {
                s += a[j];
                ans += j - i - counter[s];
                counter[s]++;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}