算法

(前缀和优化DP) $O(n^2)$

记 $dp[i][j]$ 表示前 $i$ 个数分成 $j$ 段的合法方案数，$s[i]$ 表示前 $i$ 个数的和。

转移方程：

$$dp[i][j] = \sum_{k = 0}^{i - 1} dp[k][j-1]\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;
}