我的做法：用队列线段树动态循环移位维护每个点结尾的最大前缀和，求出 $k=0$，然后脑子里画图感觉 $i\gets i+1$ 其实是若干个相同的状态复制成大小平方的矩阵，然后直接 $k$ 次平方。

die 马：

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rll register ll
#define cll const ll
#define N 2000005
#define MOD 998244353
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
ll n,k,ans,a[N],tt[N],len[2],aa[2][N];
inline ll mod(ll x){return x%MOD;};
struct node{ll tag,minn;}t[N<<2];
inline void pushup(ll p){t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);}
inline void addtag(ll p,ll k)
{
	t[p].minn+=k;
	t[p].tag+=k;
}
inline void pushdown(ll p)
{
	addtag(p<<1,t[p].tag);
	addtag(p<<1|1,t[p].tag);
	t[p].tag=0;
}
inline void change(ll p,ll l,ll r,ll ql,ll qr,ll k)
{
	if(l>=ql&&r<=qr)
	{
		addtag(p,k);
		return;
	}
	pushdown(p);
	rll mid=l+r>>1;
	if(ql<=mid) change(p<<1,l,mid,ql,qr,k);
	if(mid<qr) change(p<<1|1,mid+1,r,ql,qr,k);
	pushup(p);
}
inline ll query(ll p,ll l,ll r,ll ql,ll qr)
{
	if(l>=ql&&r<=qr) return t[p].minn;
	pushdown(p);
	rll mid=l+r>>1,ret=1e18;
	if(ql<=mid) ret=min(ret,query(p<<1,l,mid,ql,qr));
	if(mid<qr) ret=min(ret,query(p<<1|1,mid+1,r,ql,qr));
	return ret;
}
inline bool check(bool g)
{
	for(rll i=1,sum=0;i<=len[g];i++)
	{
		sum+=aa[g][i];
		if(sum<=0) return 0;
	}
	return 1;
}
inline void mv(bool g)
{
	for(rll i=1;i<=len[g];i++)
		tt[i]=aa[g][i];
	for(rll i=1;i<len[g];i++)
		aa[g][i]=tt[i+1];
	aa[g][len[g]]=tt[1];
}
inline void push(bool g)
{
	for(rll i=1;i<=len[g];i++)
		aa[g^1][++len[g^1]]=aa[g][i];
}
int main()
{
	n=read(),k=read();
	for(rll i=1,sum=0;i<=n;i++)
	{
		a[i]=a[n+i]=read();
		sum+=a[i];
		change(1,1,n*2,n+i,n+i,sum);
	}
	rll tn=n*2;
	for(rll i=1;i<=n;i++)
	{
		if(query(1,1,n*2,tn-n+1,tn)>0) ans++;
		change(1,1,n*2,tn-n,tn-1,a[tn]);
		tn--;
	}
	for(rll i=1;i<=k;i++)
		ans=mod(ans*ans);
	write(ans);
    return 0;
}

所以题解写的啥意思？

早知道 ssh 了。