算法
(前缀和优化DP) $O(n^2)$
记 $dp[i][j]$ 表示前 $i$ 个数分成 $j$ 段的合法方案数,$s[i]$ 表示前 $i$ 个数的和。
转移方程:
$$ dp[i][j] = \sum_{k = 0}^{i - 1} dp[k][j]\Big[s[i] - s[k] \equiv 0 \bmod j\Big] $$
容易发现这个转移复杂度为 $O(n)$,总复杂度为 $O(n^3)$,显然会超时。
然后注意到 $s[i] - s[k] \equiv 0 \bmod j$,可以变形为 $s[i] \equiv s[k] \bmod j$
于是,我们可以用前缀和数组 $ds[i][j]$ 来记录 $s[i] \% j$ 的方案数,也就是所有满足 $s[i] \equiv s[k] \bmod j$ 的 $dp[k][j - 1]$ 的和。这样转移就优化到了 $O(1)$。
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using namespace atcoder;
using mint = modint1000000007;
using std::vector;
using ll = long long;
const int MAX_N = 3005;
mint dp[MAX_N][MAX_N];
mint ds[MAX_N][MAX_N];
int main() {
int n;
cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(n + 1);
rep(i, n) s[i + 1] = s[i] + a[i];
dp[0][1] = 1;
ds[1][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i; j >= 1; --j) {
mint now;
// for (int k = 0; k < i; ++k) {
// if ((s[i] - s[j]) % j == 0)
// now += dp[k][j];
// }
now = ds[j][s[i] % j];
dp[i][j + 1] = now;
ds[j + 1][s[i] % (j + 1)] += now;
}
}
mint ans;
for (int j = 1; j <= n + 1; ++j) ans += dp[n][j];
cout << ans.val() << '\n';
return 0;
}