题目描述

难度分:$1700$

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

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

初始化$s=0$，然后从左到右遍历$a$。对于每个$a[i]$，你有两个选项：

1. 把$s$更新为$s+a[i]$。
2. 把$s$更新为$|s+a[i]|$。

设$s$的最大值为$k$。输出使$s=k$的方案数，模$998244353$。

两个选项得到的结果即使是一样的，也算不同的方案。

输入样例

5
4
2 -5 3 -3
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4

输出样例

12
256
1
8
16

算法

动态规划

状态定义

$f[i]$表示从$1$操作到$i$能够得到的最小值，$g[i]$表示从$1$操作到$i$能够得到的最大值。$dp_1[i]$、$dp_2[i]$分别表示能够得到$f[i]$、$g[i]$的方案数。在这个状态定义下，答案就应该是$dp_2[n]$。

状态转移

如果一路不加绝对值，得到的肯定是最小值，也就是说$f[i]=f[i-1]+a[i]$。但是当$f[i-1] \lt 0$时，在$i$位置加上绝对值有可能会超过$g[i-1]+a[i]$，因此$g[i]=max(|f[i-1]+a[i]|,|g[i-1]+a[i]|)$。这就像求连乘的最大值一样，需要同时保留前面的最大值和最小值，防止负负得正。

如果$f[i-1]+a[i] \lt 0$，那肯定是在$i$时不取绝对值能够得到最小值，有状态转移$dp_1[i]=dp_1[i-1]$。否则在$i$时可以取绝对值也可以不取绝对值，状态转移方程为$dp_1[i]=2 \times dp_1[i-1]$。

下面考虑$dp_2[i]$怎么转移。分为以下几种情况：

1. $|f[i-1]+a[i]| \lt |g[i-1]+a[i]|$，$g[i]$由$g[i-1]$得来。如果$g[i-1]+a[i] \lt 0$，那就必须要在$i$处取绝对值才能得到$g[i]$，状态转移方程为$dp_2[i]=dp_2[i-1]$。如果$g[i-1]+a[i] \geq 0$，那$i$处取不取绝对值都能得到最大值，状态转移方程为$dp_2[i]=2 \times dp_2[i-1]$。
2. $|f[i-1]+a[i]| \gt |g[i-1]+a[i]|$，$g[i]$由$f[i-1]$得来。如果$f[i-1]+a[i] \lt 0$，那就必须要在$i$处取绝对值才能得到$g[i]$，状态转移方程为$dp_2[i]=dp_1[i-1]$。如果$g[i-1]+a[i] \geq 0$，那$i$处取不取绝对值都能得到最大值，状态转移方程为$dp_2[i]=2 \times dp_1[i-1]$。
3. $|f[i-1]+a[i]|=|g[i-1]+a[i]|$，$f[i-1]$和$g[i-1]$都能得到$g[i]$。如果$f[i-1] \neq g[i-1]$，就综合以上两种情况。否则，以上两种情况就是重复的，随便选一个做转移就行。

复杂度分析

时间复杂度

状态数量是$O(n)$的，单次转移是$O(1)$的，遍历一遍数组$a$就可以求得方案数。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

四个DP矩阵$f$、$g$、$dp_1$、$dp_2$，空间都是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 998244353;
int T, n, a[N], dp1[N], dp2[N];
LL f[N], g[N];

int main() {
    scanf("%d", &T);
    for(int cases = 1; cases <= T; cases++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            f[i] = g[i] = dp1[i] = dp2[i] = 0;
        }
        f[0] = g[0] = 0;
        dp1[0] = dp2[0] = 1;
        for(int i = 1; i <= n; i++) {
            f[i] = f[i - 1] + a[i];
            LL v1 = abs(g[i - 1] + a[i]), v2 = abs(f[i - 1] + a[i]);
            g[i] = max(v1, v2);
            dp1[i] = (dp1[i] + dp1[i - 1]) % MOD;
            if(f[i - 1] + a[i] >= 0) {
                dp1[i] = (dp1[i] + dp1[i - 1]) % MOD;
            }
            if(v1 > v2) {
                dp2[i] = (dp2[i] + dp2[i - 1]) % MOD;
                if(g[i - 1] + a[i] >= 0) {
                    dp2[i] = (dp2[i] + dp2[i - 1]) % MOD;
                }
            }else if(v1 < v2) {
                dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                if(f[i - 1] + a[i] >= 0) {
                    dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                }
            }else {
                if(f[i - 1] == g[i - 1]) {
                    dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                    if(f[i - 1] + a[i] >= 0) {
                        dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                    }
                }else {
                    dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                    if(f[i - 1] + a[i] >= 0) {
                        dp2[i] = (dp2[i] + dp1[i - 1]) % MOD;
                    }
                    dp2[i] = (dp2[i] + dp2[i - 1]) % MOD;
                    if(g[i - 1] + a[i] >= 0) {
                        dp2[i] = (dp2[i] + dp2[i - 1]) % MOD;
                    }
                }
            }
        }
        printf("%d\n", dp2[n]);
    }
    return 0;
}