题解

每辆运输车装走的连续零件箱对应序列中的一段．设前缀和为

$$S_i=\sum_{t=1}^{i}a_t,\qquad S_0=0.$$

如果第 $j$ 段是区间 $(p,i]$，它合法当且仅当

$$S_i-S_p\equiv0\pmod j.$$

算法 0：枚举切分位置

相邻元素之间的 $n-1$ 个位置都可以选择切开或不断开，因此可以枚举全部 $2^{n-1}$ 个方案，再依次检查每一段．时间复杂度为 $O(n2^n)$，空间复杂度为 $O(n)$．

预期通过 subtask 1，预期得分为 $10$ 分．

算法 1：三次动态规划

令 $dp_{i,j}$ 表示将前 $i$ 个元素合法划分成恰好 $j$ 段的方案数．枚举最后一段左侧的切分位置 $p$，得到转移

$$dp_{i,j}=\sum_{\substack{0\le p<i\\S_i-S_p\equiv0\pmod j}}dp_{p,j-1}.$$

初始状态为 $dp_{0,0}=1$，最终答案为 $\sum_{j=1}^{n}dp_{n,j}$．直接枚举 $i,j,p$ 的时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$．

预期通过 subtask 1、2、3，预期得分为 $45$ 分．

算法 2：特殊序列

当所有 $a_i=0$ 时，任意连续段的和都是所有正整数的倍数，因此每个切分位置都可以独立选择，答案为 $2^{n-1}$．读取序列并快速幂计算的时间复杂度为 $O(n+\log n)$，空间复杂度为 $O(1)$．

预期通过 subtask 4，预期得分为 $10$ 分．

当所有 $a_i=1$ 时，第 $j$ 段的元素个数必须是 $j$ 的正整数倍．设 $f_{j,s}$ 表示已经确定前 $j$ 段，且它们的总长度为 $s$ 的方案数．枚举第 $j$ 段包含 $tj$ 个元素，其中 $t\ge1$，有

$$f_{j,s}=\sum_{t\ge1}f_{j-1,s-tj} =f_{j,s-j}+f_{j-1,s-j}．$$

第二个等式把枚举段长优化成了常数次转移．前 $j$ 段的最小总长度为 $1+2+\cdots+j$，所以只需要处理满足 $j(j+1)/2\le n$ 的 $O(\sqrt n)$ 层．答案为所有 $f_{j,n}$ 之和．时间复杂度为 $O(n\sqrt n)$，使用滚动数组时空间复杂度为 $O(n)$．

预期通过 subtask 5，预期得分为 $15$ 分．

算法 3：按照前缀和余数汇总

一般情况下，转移条件可以改写为

$$S_p\equiv S_i\pmod j.$$

固定段数 $j$，从左到右枚举右端点 $i$．在计算 $dp_{i,j}$ 以前，先把 $dp_{i-1,j-1}$ 加入编号为 $S_{i-1}\bmod j$ 的桶中．此时桶 $r$ 中恰好保存了所有满足 $0\le p<i$ 且 $S_p\bmod j=r$ 的 $dp_{p,j-1}$ 之和，所以

$$dp_{i,j}=\operatorname{bucket}[S_i\bmod j].$$

计算第 $j$ 层只依赖第 $j-1$ 层，可以使用两个长度为 $n+1$ 的数组滚动保存．

由于前 $j-1$ 段至少需要 $j-1$ 个元素，计算第 $j$ 层时可以让 $i$ 从 $j$ 开始枚举．前缀和最大为 $5\times10^{12}$，需要使用 64 位整数保存；方案数和余数桶则始终对 $998244353$ 取模．

正确性证明

根据状态定义，任意合法的前 $i$ 个元素、$j$ 段划分都有唯一的最后切分位置 $p$；它的前 $j-1$ 段贡献 $dp_{p,j-1}$，且最后一段合法恰好等价于 $S_p$ 与 $S_i$ 模 $j$ 同余．反过来，桶中每个被累加的状态与区间 $(p,i]$ 拼接后都会形成一个合法且唯一的 $j$ 段方案．因此桶查询不重不漏地实现了三次 DP 的转移．初始状态和答案汇总与划分定义一致，所以算法正确．

共有 $n$ 层，每层扫描 $n$ 个右端点，时间复杂度为 $O(n^2)$．滚动数组、前缀和与当前层的余数桶均为 $O(n)$ 大小，空间复杂度为 $O(n)$．

预期通过所有 subtask，预期得分为 $100$ 分．

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

constexpr int MOD = 998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<std::int64_t> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        std::int64_t x;
        std::cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    std::vector<int> previous(n + 1, 0), current(n + 1, 0);
    previous[0] = 1;
    int answer = 0;

    for (int segments = 1; segments <= n; ++segments) {
        std::vector<int> bucket(segments, 0);
        std::fill(current.begin(), current.end(), 0);
        for (int i = segments; i <= n; ++i) {
            int previous_remainder = static_cast<int>(prefix[i - 1] % segments);
            bucket[previous_remainder] += previous[i - 1];
            if (bucket[previous_remainder] >= MOD) bucket[previous_remainder] -= MOD;

            int current_remainder = static_cast<int>(prefix[i] % segments);
            current[i] = bucket[current_remainder];
        }
        answer += current[n];
        if (answer >= MOD) answer -= MOD;
        previous.swap(current);
    }

    std::cout << answer << '\n';
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e3+5,mod=998244353;//M=2e3+5;//inf=1e9+5;
ll qzh[N];
int cur[N],pre[N]; 
int main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
    	int x;cin>>x;
    	qzh[i]=qzh[i-1]+x;
	}
	pre[0]=1;
	ll ans=0;
	for(int i=1;i<=n;i++){
		memset(cur,0,sizeof(int)*(n+1));
		vector<int> cnt(i,0);
		if(i==1) cnt[0]=1;
		for(int j=1;j<=n;j++){
			int k=qzh[j]%i;
			cur[j]=cnt[k];
			cnt[k]=(cnt[k]+pre[j])%mod;
		}
		ans=(ans+cur[n])%mod;
		memcpy(pre,cur,sizeof(int)*(n+1));
	}
	cout<<ans<<'\n';
	return 0;
}