自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:38:28，当前版本为作者最后更新于2022-05-26 16:47:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先考虑给定 $a,b$ 怎么算答案。

令 $c,d$ 分别为 $a,b$ 的前缀和，那么答案即为：

$$\sum\limits_{i=1}^nw_i|c_i-d_i|$$

题目中给定了 $a$，于是 $c$ 也可以求出来。

令 $m=c_n$，即题目中的 $S$。

根据期望的线性性，我们可以枚举 $i,d_i$ 算贡献。一对 $i,d_i$ 出现的条件是前 $i$ 个数和为 $d_i$ 且后 $n-i$ 个数和为 $m-d_i$。这个是经典问题，可以用插板法解决。那么答案可以表示为：

$$\sum\limits_{i=1}^nw_i\sum\limits_{j=0}^{m}|j-c_i|\dbinom{i+j-1}{i-1}\dbinom{n-i+m-j-1}{n-i-1} $$

此时我们已经得到了一个 $O(nm)$ 的做法，可以得到 $40\operatorname{pts}$。

我们可以只考虑 $j\le c_i$ 的部分，$j>c_i$ 的部分可以类似解决。

令

$$f(n,m,i,k)=\sum\limits_{j=0}^{k}\dbinom{i+j-1}{i-1}\dbinom{n-i+m-j-1}{n-i-1} $$$$g(n,m,i,k)=\sum\limits_{j=0}^{k}j\dbinom{i+j-1}{i-1}\dbinom{n-i+m-j-1}{n-i-1} $$

我们只需要对于每一个 $i$ 算出 $f(n,m,i,c_i)$ 和 $g(n,m,i,c_i)$ 就行了。

可以注意到：

$$j\dbinom{i+j-1}{i-1}=j\dbinom{i+j-1}{j}=i\dbinom{i+j-1}{i} $$

代入可得：

$$g(n,m,i,k)=i\sum\limits_{j=0}^{k}\dbinom{i+j-1}{i}\dbinom{n-i+m-j-1}{n-i-1} $$$$=i\sum\limits_{j=0}^{k-1}\dbinom{i+j}{i}\dbinom{n-i+m-j-2}{n-i-1} $$$$=i\times f(n+1,m-1,i+1,k-1)$$

因此我们只需要解决 $f$ 即可。

我们可以用类似于莫队的思想，每次将 $i$ 或者 $k$ 变化 $1$，同时维护答案。

因为 $c$ 是单调不降的，所以我们这种移动只会有 $O(n+m)$ 次。

$k$ 变化是很好处理的，只需要按照 $f$ 的表达式直接计算即可。

$i$ 变化就不那么好处理了，怎么办呢！

换一个角度考虑 $f$。

$f(n,m,i,k)$ 的组合意义是前 $i$ 个数和 $\le k$ 且所有 $n$ 个数和为 $m$ 的方案数。

其实就是把 $m$ 个无序的小球放进 $n$ 个有序的盒子里，要求前 $i$ 个盒子里的小球总数不超过 $k$。

而这相当于从左往右第 $k+1$ 个小球不在前 $i$ 个盒子里！

枚举第 $k+1$ 个小球放在哪个盒子里，可以得到：

$$f(n,m,i,k)=\sum\limits_{j=i+1}^n\dbinom{j+k-1}{j-1}\dbinom{n-j+m-k-1}{n-j} $$

此时 $i$ 变化的解决方案已经显而易见了！

于是，我们在 $O(n+m)$ 的时间复杂度内解决了本题。

当然如果你是 nb 老哥，直接对着式子硬推据说也是能做的！