题解：CF1984C2 Magnitude (Hard Version)

Lucas_Fan_2013 · 2026-11-12 20:59:19 · 题解

思路

观察易得，只有在 a_i < 0 且 \lvert a_i \rvert > c 时，操作 2 与操作 1 才有区别。

也就是说，只有到了第 i 个位置（1 \le i \le n），满足 1 到 i 的前缀和 b_i < 0 时，才会进行操作 2。

题目要求最大值的不同操作个数。

最大值：我们找到最小的 b_i，使用操作 2，这样可以让最小值变大，最后可以得到最大值。

我们维护所有最小的 b_i。

对于每个 b_i：

• 对于 a_j（1 \le j < i），只有 b_j \ge 0 时使用操作 2 不改变最大值。（显然）

• 对于 a_j（i < j \le n），不管 b_j 取何值，都不影响。

::::info[为什么对于 1 < j \le n，b_j 的值不影响结果？]

因为我们执行了一次操作 2，所以使结果变成正数。（后续的前缀和向上平移，不影响与 b_n 的斜率）

所以，若与 b_n 呈下降趋势，则平移回来，此时发现 b_n < b_j。

因为 b_j 为最小的前缀和，故不可能，矛盾。

证毕。

::::

上述所有满足条件的 a_j 都可以进行操作 1 或进行操作 2，每个位置互不影响，并且不影响答案。

我们记 cnt_i（1 \le i \le n）为 1 到 i，b_i \ge 0 的个数。

于是单个 b_i 的答案为 2^{cnt_{i-1}} \times 2^{n-i}。（用快速幂维护）

最后把所有前缀和最小的 b_i 答案累加起来即可。

若对于所有 1 \le i \le n，皆有 b_i \ge 0，还需特判。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,mod=998244353;
int t;
int n;
int a[N],b[N]; // b表示前缀和
int ksm(int a,int b){ // 快速幂
    int res=1;
    while (b>0){
        if (b&1==1) res=res%mod*a%mod;
        a=a%mod*a%mod,b>>=1;
    }
    return res;
}
int ans;
signed main(){
    cin>>t;
    while (t--){
        cin>>n,ans=0,b[0]=0;
        int cnt=0,zx=0;
        for (int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        for (int i=1;i<=n;i++) b[i]+=b[i-1],zx=min(zx,b[i]);
        if (zx>=0){
            cout<<ksm(2,n)<<endl;
            continue;
        }
        for (int i=1;i<=n;i++){
            if (zx==b[i]){
                ans=(ans+ksm(2,cnt)%mod*ksm(2,n-i)%mod)%mod;
            }
            if (b[i]>=0) cnt++;
        }
        cout<<ans<<endl;
    }
    return 0;
}