赛时 50pts 求助
查看原帖
赛时 50pts 求助
398190
lanretE楼主2022/10/23 16:55

大阳历能过,复杂度没问题,看不出来哪里错了/kk

#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int N=1e7+10,p=998244353;
int n,k;
int a[N],l,r,sum,squ,cnt,squ1,sum1;
signed main(){
    // freopen("ex.in","r",stdin);
    // freopen("[].out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        if(a[i]>=0){
            sum=(sum+a[i])%p;
            squ=(squ+a[i]*a[i])%p;
            ++cnt;
        }
        else{
            squ1=(squ1+a[i]*a[i]%p)%p;
            sum1=(sum1+a[i])%p;
        }
        if(cnt==1) l=i;
    }
    // cout<<squ<<' '<<sum<<endl;
    int ans=0;
    ans=(ans+2*sum1+n-cnt)%p;
    // cout<<ans<<endl;
    r=n;
    for(int i=1;i<=k;++i){
        squ=(squ+2*sum+r-l+1)%p;
        sum=(sum+r-l+1)%p;
        while(l>=2 && abs(a[l-1]+i)>abs(a[l-1])){
            // cout<<333333<<endl;
            // cout<<a[l-1]+i<<endl;
            sum=(sum+a[l-1]+i)%p; squ=(squ+(a[l-1]+i)*(a[l-1]+i))%p;
            squ1=(squ1+p-a[l-1]*a[l-1]%p)%p;
            --l;
        }
        // cout<<squ<<' '<<sum<<' '<<squ1<<endl;
        ans=(ans+squ)%p; 
        ans=(ans+squ1)%p;
        // cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

有没有神仙帮忙看看

2022/10/23 16:55
加载中...