自动搬运

查看原文

来自洛谷，原作者为

	wdgm4 脑子好使，拜谢脑子

搬运于2025-08-24 22:40:28，当前版本为作者最后更新于2022-10-23 17:01:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考试时没考虑到会爆 long long ，痛失 30 分，发题解留个纪念。

暴力的思路

我首先思考如何暴力（首先提醒，暴力会超时，但可以从暴力出发引出正解,反正我考试时先打的暴力，再去探索 AC 思路，如果想直接看 AC 思路可以跳过），题目中说如果将 $a$ 分成 $m$ 段（可以有空段），并从前往后第 $i$ 段内的每个数都加上 $i$。我考试时读到这，一个邪恶的贪心思路浮出我的脑海。例如题目样例，我们可以像下面这样：

[-3][][]....[][1,2,2]

利用贪心，我们让负数都放在最左面的一段里，让正数放在最右面的一段里，这样既能保证负数在加 $i$ 后还为负数时平方最大，正数平方最大。但有可能负数加上 $i$ 变为正数且它的平方比原来的平方大，所以我们只需要加一个判断即可。

超时代码

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int n,k;
const int mod=998244353;
long long a[1000010],ans;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	} 
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(abs(a[j]+1)>abs(a[j]+i)){//判断放最左面还是最右面
				ans+=(a[j]+1)*(a[j]+1);
				ans%=mod;
			}else{
				ans+=(a[j]+i)*(a[j]+i);
				ans%=mod;
			}
		}
	}
	cout<<ans;
	return 0;
}

时间复杂度：$O(nk)$。

当然，由于是暴力，我们只能得 30 分，其他全部 TLE。看来需要优化一下了。

AC思路

让我们返回到题目界面（传送门），题目中要算的公式整理为 $\sum\limits_{i=1}^k {\sum\limits_{j=1}^na_j^2}$（其中 $a_j$ 的值随 $i$ 的变化而变化），我们简单转换一下，变成 $\sum\limits_{i=1}^n{\sum\limits_{j=1}^ka_i^2}$（其中 $a_i$ 的值随 $j$ 的值变化而变化），而在新算式中，$\sum\limits_{j+1}^ka_i^2$ 能够用 $O(1)$ 的复杂度算出来。

我们可以先用一个前缀和 $b$，$b_i$ 表示前 $i$ 个数的平方的和。计算时分两种情况：

• 如果 $a_i$ 大于等于 $0$，在分段中放在最右面一定最优，所以用前缀和计算即可。

• 如果 $a_i$ 小于 $0$，在分段时最优的分段位置不同，需要特殊判断（具体内容请看代码）。

思路就先差不多，下面放下代码。

code

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
long long n,k;
long long m,f;
const long long mod=998244353;
const int MAXN=20000000;
long long a[1000010];
long long ans,num;
int b[20000010];//前缀和
int main(){
	cin>>n>>k;
	for(long long i=1;i<=MAXN;i++){
		b[i]=(b[i-1]+i*i%mod)%mod;//计算前缀和
	}
	for(register int i=1;i<=n;i++){
		num=0;
		scanf("%lld",&a[i]);
		if(a[i]<0){//分情况讨论
			m=(a[i]+1)*(-2)+1;
			f=-(a[i]+1);
			num+=min(m,k)*1ll*f%mod*f;//注意这里一定要取模一次，不然会爆long long
			num%=mod;
			if(k>m){
				num+=(b[k-m+f]*1ll-b[f]+mod)%mod;
				num%=mod;
			}
		}else{
			num+=(b[a[i]+k]*1ll-b[a[i]]+mod)%mod;
			num%=mod;
		}
		ans+=num;
		ans%=mod;
	} 
	cout<<ans%mod;
	return 0;
}

时间复杂度：$O(n)$（还要加一个计算前缀和的大常数）

注意事项

1. 注意取模问题，算减法取模时要先加上 $mod$ 再取模。

2. 在几个数连乘时，要记得在中间取模，不然会爆 long long，然后痛失 30 分。

3. 前缀和数组千万不要开 long long，不然你会MLE。