【P8367】[LNOI2022] 盒 胡扯

· · 个人记录

原题链接

本文应该是要配图的，但是笔者懒得搞，建议是找一张草稿纸画画就懂了。

试图用更形象的角度分析问题。

首先我们所求的式子是：

\sum_{i=1}^{n-1} w_i \sum_{j=0}^{S}|pre-j|\binom{j+i-1}{j}\binom{n-i+S-j-1}{S-j}

其中 pre 为前缀和。

拆掉绝对值，先只计算 j < pre，然后 reverse 整个数组再做一遍。也就是求：

\sum_{i=1}^{n-1} w_i \sum_{j=0}^{pre}(pre-j)\binom{j+i-1}{j}\binom{n-i+S-j-1}{S-j}

发现这个式子后半部分有点类似组合数行前缀和的问题，考虑用那个莫队做法类似的方式，每次移动 i \leftarrow i+1 或 pre \leftarrow pre+1，维护后面一坨的值，总共要移动 O(n+S) 次。

考虑怎么移动。

将 b 数组一一对应到在一张大小为 n\times(S+1) 的网格图上的一条从左上角走到右下角的路径，记左上角为 (1,0)，右下角为 (n,S)

那么原式就相当对每一条路径，考虑他走过的那一条 (i,j) 到 (i+1,j) 的边，会产生 max(0,pre-j) 的贡献。

先考虑一个简单的形式，也就是贡献为 [pre > j]，那么考虑当 pre \leftarrow pre+1 时，增加的贡献显然就是经过 (i,pre) 到 (i+1,pre) 这条边的路径数量，而当 i\leftarrow i+1 时，考虑有多少路径贡献发生变化，显然这条路径经过 (i,j) 到 (i+1,j)(j < pre) 而且经过了 (i+1,k) 到 (i+2,k)(j \ge pre)。在纸上比划一下，发现这条路径等价于一定经过 (i+1,pre-1) 到 (i+1,pre)。

于是我们解决了这个更简单的形式。考虑原本的形式，记为 v1，当 pre \leftarrow pre+1 是，所有经过 (i,j) 到 (i+1,j)(j \le pre) 的路径贡献全部增加 1，这样的路径的条数我们上一段就求出来了，记为 v2。当 i \leftarrow i+1 时，发现每经过一条 (i+1,j) 到 (i+1,j+1)(j < pre) 的边，贡献就会 -1，那么枚举这样的一条边，可以把代数形式写出来，也可以视选择这条产生贡献的边为一条向下的边，都可以转化为上一段的形式，这里就不再赘述。这个贡献的变化量记为 v3。在移动 i 和 pre 的时候同时维护 v1,v2,v3 即可。