P8367 [LNOI2022] 盒

· · 题解

首先考虑给定 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) 次。

$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 老哥，直接对着式子硬推据说也是能做的！