AtCoder Beginner Contest 207 E
题意：
? 给定一个长度为 \(n\) 的数列 \(a\)。 我们将 \(a\) 按顺序分成若干个数列 \(b_1,b_2\cdots b_k\)，对于每一个数列 \(b_i\)，必定满足 \(b_i\) 中所有数字之和被 \(i\) 整除。求合法分割的总方案，由于答案过大，输出总方案 \(\bmod \;10^9+7\)。 \((1\le N \le3000,1\le A_i\le10^{15})\)。
? 很明显的一个 dp 题，我们可以敲出一个暴力的转移式：
\[dp_{i,j}=\sum_{k=1}^{i-1}{dp_{k,j-1}}\;((sum_i-sum_k)\bmod j = 0)
\]
? 其中 \(dp_{i,j}\) 表示当前枚举到第 \(i\) 位且到第 \(i\) 位为止是第 \(j\) 个数列。那么这样的一个转移式需要我们去枚举 \(i,j,k\)，显然，这么做的时间复杂度是 \(O(n^3)\)。我们承受不了这么大的时间复杂度，考虑优化。
? 注意到当 \((sum_i-sum_k)\bmod j =0\) 时，一定有 \(sum_i \equiv sum_ k\mod j\)。由于 \(j\) 的数值很小，所以我们可以在最外部枚举 \(j\)，开一个桶 \(f_i\) 表示满足 \(sum_k \bmod j =i\) 所有 \(dp_{k,j-1}\) 的值，这样我们可以 \(O(1)\) 进行转移。总时间复杂度为 \(O(n^3)\)。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e3+5;
const int MOD = 1e9+7;
int n,dp[MAXN][MAXN],f[MAXN];
ll sum[MAXN],a[MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+a[i];
dp[0][0]=1;
for(int k=1;k<=n;++k)
{
for(int i=0;i<=n;++i) f[i]=0;
for(int i=0;i<=n;++i)
{
dp[i][k]=f[sum[i]%k];
f[sum[i]%k]=(f[sum[i]%k]+dp[i][k-1])%MOD;
}
}
ll ans=0;
for(int i=1;i<=n;++i)
ans=(ans+dp[n][i])%MOD;
printf("%lld",ans);
return 0;
}