题目大意
给定一个序列 \(a\)，问将其划分成若干段，满足第 \(i\) 段的和是 \(i\) 的倍数的划分方案的个数。
思路分析
考虑 DP，设 \(f_{i,j}\) 表示将序列中前 \(i\) 个数划分成 \(j\) 段，且满足条件的划分方案的个数，容易得出状态转移方程：
\[f_{i,j}=\sum f_{k,j-1}(\sum_{h=k+1}^i a_i\bmod j=0)
\]
直接转移的复杂度是 \(O(n^3)\) 的，无法接受，考虑优化。
设 \(s_i\) 为 \(a\) 的前 \(i\) 项和，那么约束条件等价于 \((s_i-s_k) \bmod j=0\)，当条件成立时有 \(s_i\equiv s_k \pmod j\)。
可以设 \(g_{i,j}=\sum f_{k,i}(s_k\bmod (i+1)=j)\)，那么容易发现
\[g_{j-1,s_i\bmod j}=\sum f_{k,j-1}(s_k\bmod j=s_i\bmod j)= f_{i,j}
\]
这样转移就优化到了 \(O(n^2)\)，这是因为 \(g\) 可以在转移时累加，即
\[g_{j,s_i\bmod (j+1)}=\sum f_{k,j}(s_k\bmod (j+1)=s_i\bmod(j+1))
\]
其中包含 \(f_{i,j}\)。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=3200,mod=1000000007;
#define int long long
int f[N][N],g[N][N];
int sum[N],a[N];
int ans,n;
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
f[0][0]=g[0][0]=1;//初始条件
for(int i=1;i<=n;i++)
for(int j=n;j>=1;j--){
f[i][j]=g[j-1][sum[i]%j];
g[j][sum[i]%(j+1)]=(g[j][sum[i]%(j+1)]+f[i][j])%mod;
}
for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod;//累加答案
cout<<ans<<'\n';
return 0;
}