题解
由于使用操作二会让负数变成正数,所以我们考虑让操作二在c最小且为负数的点使用
在使用完操作二之后,之后的c肯定非负,所以在此之后两种操作都可以使用
实施
先判断存不存在c最小且为负数的点,然后再统计所有c最小且为负数的点的贡献
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll mod = 998244353;
ll a[MAXN];
ll pre[MAXN] = {0};
// 快速幂计算
ll qpow(ll base, ll exp) {
ll result = 1;
base %= mod; // 取模
while (exp > 0) {
if (exp % 2 == 1)
result = (result * base) % mod; // 取模
base = (base * base) % mod; // 取模
exp /= 2;
}
return result;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pre[i] = pre[i-1] + a[i];
}
int pos = 1;
for (int i = 2; i <= n; i++) {
if (pre[i] < pre[pos]) pos = i;
}
if(pre[pos]>=0)
{
cout<<qpow(2,n)%mod<<endl;
continue;
}
ll ans=0,tem=1;
for(int i=1;i<=n;i++)
{
if(pre[i]>=0) tem<<=1;
tem%=mod;
if(pre[i]==pre[pos]) ans+=tem*qpow(2,n-i)%mod;
ans%=mod;
}
cout << ans % mod << endl; // 结果取模
}
return 0;
}
标签:Version,exp,int,ll,Magnitude,result,base,C2,mod
From: https://www.cnblogs.com/pure4knowledge/p/18241952