题解：P16433 [APIO 2026 中国赛区] 上升

· · 题解

直接贡献延迟，快进到你已经推好转移方程，这种做法是代数硬推枚举一段加合并的做法。

区间 [l,r] 端点值给定分别为 a_l=L,a_r=R，中间全是 0 的情况下：

令 f_{j,k} 表示第一个数相对排名是 j，最后一个数相对排名是 k 的贡献和，g_x 表示 [1,r] 中值域 [1,a_r] 有 x 个数留下来给后面填：

g'_x=\sum_{j,k,i,x}g_{x+i+k-R+L-1}f_{j,k}\binom{R-L-1}{k-j-1}\binom{R-L+j-k}{i}\binom{x+i+k-R+L-1}{j-1}\binom{x+r-R}{-k+r-l+1}

把式子搞得好看一点。

这种先把很长一堆的给换元了，不然看着很难受也很难推。也就是说令 i:=x+i+k-R+L-1。

\begin{aligned}g'_x=\sum_{j,k,i}g_{i}f_{j,k}\binom{R-L-1}{k-j-1}\binom{R-L+j-k}{i-x-k+R-L+1}\binom{i}{j-1}\binom{x+r-R}{-k+r-l+1}\end{aligned}

中间这个组合数 \binom{R-L+j-k}{i-x-k+R-L+1} 太长了，给他换一下成 \binom{R-L+j-k}{x+j-i-1}。

\begin{aligned}g'_x=\sum_{j,k,i}g_{i}f_{j,k}\binom{R-L-1}{k-j-1}\binom{R-L+j-k}{x+j-i-1}\binom{i}{j-1}\binom{x+r-R}{-k+r-l+1}\end{aligned}

从这里开始开始优化了

看一下每个组合数里的变量，发现 \binom{R-L+j-k}{x+j-i-1} 把所有变量捆一起了。

考虑逆用范德蒙德卷积，把 j 直接剥离出来。但是这样会新引入一个变量，因此还是 4 个变量。但是拆了过后的 u 只在下指标上，所以可以换元。

和 \binom{i}{j-1} 用一下指标交换律，这样可以让 j-1 只在一个组合数里，因此上标拆出来 j-1。

\begin{aligned}\binom{R-L+j-k}{x+j-i-1}=\sum_{u}\binom{j-1}{j-1-u}\binom{R-L+1-k}{x-i+u}=\sum_{u}\binom{j-1}{u}\binom{R-L+1-k}{x-i+u}\end{aligned}

那么总式为：

g'_x&=\sum_{j,k,i,u}g_{i}f_{j,k}\binom{R-L-1}{k-j-1}\binom{i}{j-1}\binom{j-1}{u}\binom{R-L+1-k}{x-i+u}\binom{x+r-R}{-k+r-l+1}\\ &=\sum_{j,k,i,u}g_{i}f_{j,k}\binom{R-L-1}{k-j-1}\binom{i}{u}\binom{i-u}{j-1-u}\binom{R-L+1-k}{x-i+u}\binom{x+r-R}{-k+r-l+1}\\ \end{aligned}

换元 d=i-u：

g'_x=\sum_{j,k,d,u}g_{u+d}f_{j,k}\binom{R-L-1}{k-j-1}\binom{u+d}{u}\binom{d}{j-1-u}\binom{R-L+1-k}{x-d}\binom{x+r-R}{-k+r-l+1}\\ \end{aligned}

现在组合数可以分步计算了！！！

g'_x=\sum_{k}\binom{x+r-R}{-k+r-l+1}\sum_{d}\binom{R-L+1-k}{x-d}\sum_{j}f_{j,k}\binom{R-L-1}{k-j-1}\sum_{u}g_{u+d}\binom{u+d}{u}\binom{d}{j-1-u} \end{aligned}

从里往外计算这些和式。

枚举 d,j,u，令 f1_{d,j} 表 \begin{aligned}\sum_{u}g_{u+d}\binom{u+d}{u}\binom{d}{j-1-u}\end{aligned}，这个是 \mathcal{O}(n^2m) 的。

枚举 k,d,j，令 f2_{k,d} 表 \begin{aligned}\sum_{j}f_{j,k}\binom{R-L-1}{k-j-1}f1_{d,j}\end{aligned}，这个是 \mathcal{O}(nm^2) 的。

那么最后枚举 x,k,d，g'_x=\sum_{k}\binom{x+r-R}{-k+r-l+1}\sum_{d}\binom{R-L+1-k}{x-d}f2_{k,d}，这个是 \mathcal{O}(n^2m) 的。