题目分析

问题本质

统计所有满足 $\sum b_i = S$ 的非负整数数组 $(b_1,\dots,b_n)$ 的最小移动代价之和。

关键观察

最小代价的数学表达

定义前缀和：

• $A_i = \sum_{j=1}^i a_j$（初始状态的前缀和）
• $B_i = \sum_{j=1}^i b_j$（目标状态的前缀和）

则从位置 $i$ 到 $i+1$ 的净流量为：

$$f_i = A_i - B_i$$

最小移动代价为：

$$\operatorname{val}(b) = \sum_{i=1}^{n-1} w_i \cdot |A_i - B_i| $$

问题重新表述

需要计算：

$$\sum_{b_1+\cdots+b_n=S} \sum_{i=1}^{n-1} w_i \cdot |A_i - B_i| = \sum_{i=1}^{n-1} w_i \cdot \sum_{b_1+\cdots+b_n=S} |A_i - B_i| $$

算法框架

解法：独立计算每个分割位置的贡献

步骤1：固定位置i的分析 对于固定的 $i$，需要计算：

$$C_i = \sum_{b_1+\cdots+b_n=S} |A_i - B_i|$$

其中 $B_i = \sum_{j=1}^i b_j$。

步骤2：变量分离 将问题分解为：

• 前 $i$ 个盒子的货物数：$B_i = k$
• 后 $n-i$ 个盒子的货物数：$S - k$

则：

$$C_i = \sum_{k=0}^S |A_i - k| \cdot \binom{k+i-1}{i-1} \cdot \binom{S-k+n-i-1}{n-i-1} $$

解释：

• $|A_i - k|$：位置 $i$ 的代价贡献
• $\binom{k+i-1}{i-1}$：前 $i$ 个盒子放 $k$ 个货物的方案数（隔板法）
• $\binom{S-k+n-i-1}{n-i-1}$：后 $n-i$ 个盒子放 $S-k$ 个货物的方案数

步骤3：绝对值处理 将求和拆分为两部分：

$$C_i = \sum_{k=0}^{A_i} (A_i - k) \cdot F(i,k) + \sum_{k=A_i+1}^S (k - A_i) \cdot F(i,k) $$

其中 $F(i,k) = \binom{k+i-1}{i-1} \cdot \binom{S-k+n-i-1}{n-i-1}$

算法细节

组合数预处理

由于 $S \leq 2\times 10^6$，可以预处理：

• 阶乘数组：$fact[0..S+n]$
• 逆元数组：$invfact[0..S+n]$
• 组合数计算：$C(n,k) = fact[n] \cdot invfact[k] \cdot invfact[n-k]$

求和优化

对于每个 $i$，需要高效计算：

$$\sum_{k=0}^{A_i} F(i,k) \quad \text{和} \quad \sum_{k=0}^{A_i} k \cdot F(i,k) $$

可以利用组合恒等式和前缀和技巧：

恒等式1：$\sum_{k=0}^S F(i,k) = \binom{S+n-1}{n-1}$（总方案数）

恒等式2：$\sum_{k=0}^S k \cdot F(i,k) = \frac{S \cdot i}{n} \cdot \binom{S+n-1}{n-1}$

递推关系

观察到 $F(i,k)$ 满足递推关系：

$$F(i,k) = F(i-1,k) \cdot \frac{i-1}{i} \cdot \frac{S-k+n-i}{S-k+n-i-1} $$

可以利用这个关系在 $i$ 变化时快速更新求和。

复杂度分析

时间复杂度

• 预处理阶乘和逆元：$O(S+n)$
• 对每个 $i$ 计算 $C_i$：$O(1)$ 或 $O(\log S)$
• 总复杂度：$O(n + S)$

空间复杂度

• 阶乘数组：$O(S+n)$
• 前缀和数组：$O(S)$
• 总空间：$O(S+n)$

特殊情况处理

边界情况

• $i=1$：$B_1 = b_1$，$C_1 = \sum_{b_1=0}^S |a_1 - b_1| \cdot \binom{S-b_1+n-2}{n-2}$
• $i=n-1$：$B_{n-1} = S - b_n$，类似处理

大数处理

• 所有计算在模 $998244353$ 下进行
• 注意组合数可能很大，需要及时取模
• 使用费马小定理计算逆元

实现策略

分阶段实现

1. 预处理：计算阶乘、逆元、组合数
2. 初始化：计算 $i=1$ 时的求和
3. 递推计算：利用递推关系快速计算其他 $i$ 的 $C_i$
4. 答案统计：$\text{ans} = \sum_{i=1}^{n-1} w_i \cdot C_i$

优化技巧

• 使用递推避免重复计算
• 利用对称性：$F(i,k) = F(n-i,S-k)$
• 预计算关键的前缀和

特殊性质利用

性质A（$w_i=1$）

问题简化为计算 $\sum_{i=1}^{n-1} C_i$，可以进一步优化。

性质B（只有后20个$a_i$非零）

$A_i$ 在大部分位置为0，可以特殊处理。

性质C（最多20个非零$a_i$）

只有少数 $i$ 需要计算 $C_i$，其他位置贡献为0。

总结

本题的核心在于将物理移动问题转化为组合计数问题。通过分析发现最小代价可以表示为前缀和差值的绝对值之和，进而将问题分解为独立计算每个分割位置的贡献。利用组合恒等式和递推关系，可以在 $O(n+S)$ 时间内解决问题。关键难点在于发现 $C_i$ 的组合表达式和设计高效的求和方法。