95pts 输出负数求助
查看原帖
95pts 输出负数求助
263414
Sktic楼主2022/10/24 22:22

加了一坨取模。已经到我的取模寄限了,但是还是wa了一个点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const ll mod=998244353;
ll a[maxn],aa[maxn],as[maxn];
ll n,k,pos=0;
void upd(ll m)
{
	while(pos>=1&&abs(a[pos]+1ll)<abs(a[pos]+m))
		pos--;
	pos++;
	return;
}
ll fk()
{
	return (aa[pos-1ll]%mod+pos%mod-1ll+2ll%mod*as[pos-1ll]%mod)%mod;
}
ll dk(ll m)
{
	return ((aa[n]%mod-aa[pos-1ll]%mod)%mod+((m%mod*m%mod)%mod*(n%mod-pos%mod+1ll)%mod)%mod+(2ll*m%mod)%mod*(as[n]%mod-as[pos-1]%mod)%mod)%mod; 
}
int main()
{
//	freopen("ex.in","r",stdin); 
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		if(a[i]<0)
			pos=i;
	pos++;
	for(int i=1;i<=n;i++)
	{
		aa[i]=((a[i]%mod*a[i]%mod)%mod+aa[i-1]%mod)%mod;
		as[i]=(a[i]%mod+as[i-1]%mod)%mod;
	}
	ll ans=0;
	for(int i=1;i<=k;i++)
	{
		upd(i);
		ans=(ans%mod+fk()%mod+dk(i)%mod)%mod;
	}
	cout<<ans%mod<<endl; 
	return 0;
}
2022/10/24 22:22
加载中...