My Blogs
P8367 [LNOI2022] 盒
旧题新做，发现仍然是唯一真神。
首先考虑给定了 $b$ 序列如何计算答案，把 $a,b$ 都做一遍前缀和，则答案即为 $\sum_{i=1}^nw_i\lvert a_i-b_i\rvert$。对每个位置 $i$ 算贡献，枚举 $j=b_i$：
\[\begin{aligned} f(i,n,m,k)&=\sum_{j=0}^{k}\binom{j+i-1}{i-1}\binom{m+n-j-i-1}{n-i-1}\\ g(i,n,m,k)&=\sum_{j=k+1}^mj\binom{j+i-1}{i-1}\binom{m+n-j-i-1}{n-i-1}\\ &=\binom{m+n-1}{n-1}-\sum_{j=0}^kj\binom{j+i-1}{i-1}\binom{m+n-j-i-1}{n-i-1}\\ \end{aligned}\]对于每个 $i$ 这样暴力求 $f(i,n,m,a_i)$ 和 $g(i,n,m,a_i)$ 的时间复杂度是 $\mathcal O(nm)$。
考虑如何优化。首先对 $g_i$ 的后面部分应用吸收恒等式：
\[\begin{aligned} g(i,n,m,k)&=i\sum_{j=0}^k\binom{j+i-1}{i}\binom{m+n-j-i-1}{n-i-1}\\ &=i\sum_{j=0}^{k-1}\binom{j+i}{i}\binom{m+n-j-i-2}{n-i-1}\\ &=if(i+1,n+1,m,k-1)\\ \end{aligned}\]所以只需要求 $f$。注意到 $i$ 是不断 $+1$，而因为 $a_i$ 做完前缀和之后是单增的，所以 $j$ 的上界也是单增的。所以每次 $a_i$ 增加可以算出这个式子的增量，均摊时间复杂度是 $\mathcal O(m)$ 的。但是当 $i$ 改变了似乎没有办法维护出新的值。
考虑组合意义，$f(i,n,m,k)$ 的意义是从坐标原点开始走，只能向右，上走，走到 $x=i-1$ 的时候，$y\leq k+i-1$。枚举 $j$ 实际上就是枚举 $x=i-1$ 时的纵坐标。然后钦定它向右走一步（不然会算重）并且最终走到 $(n-1,m)$ 的方案数。
所以可以枚举纵坐标 $=k$ 时，横坐标最大的点是多少：
\[f(i,n,m,k)=\sum_{j=i}^{n-1}\binom{j+k}{k}\binom{m-k+n-2-j}{n-1-j}\]这样就可以在 $i$ 变化的时候维护增量了，总复杂度 $\mathcal O(n+m)$。