#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=998244353;
const int MN=2005;
long long n,ans,num,a[MN],dp[MN][MN],s[MN];
//前i个数分成j段最多的办法
int main(){
	scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	dp[1][1]=1;
	for(int r=2; r<=n; r++)
		for(int l=1; l<=r; l++){
			num=s[r]-s[l-1];
			for(int j=1; j<=l; j++) if(num%j==0) dp[r][j]=max(dp[r][j],(dp[l-1][j-1]+dp[l-1][j])%mod);
		}
	for(int i=1; i<=n; i++) ans=(ans+dp[n][i])%mod;
	printf("%lld",ans);
	return 0;
}

帮我把时间复杂度降到 $O(n^2)$。

这段代码大概就是说给定一个长度为 $n$ 的数组 $a$，求把 $a$ 分成若干段使得第 $i$ 段的内的数字总和为 $i$ 的倍数的方案数