列表生成：题解

思路

对 $a,b$ 同时作差分。若原数组长度为 $k$，就得到 $l=k-1$ 个二维向量 $(x_i,y_i)$，满足

$$x_i,y_i\ge0,\quad (x_i,y_i)\ne(0,0),\quad \sum x_i=n,\quad\sum y_i=m.$$

因此问题等价于：枚举由若干非零二维步组成、从 $(0,0)$ 走到 $(n,m)$ 的路径，并累加路径顶点数。

做法

二维 DP

令 $c_{i,j}$ 为走到 $(i,j)$ 的路径数，$s_{i,j}$ 为这些路径的顶点数之和。把 $(0,0)$ 看成一条含一个顶点的空路径，则 $c_{0,0}=s_{0,0}=1$。对其他格子，前驱可以是左上矩形中的任意不同格子：

$$c_{i,j}=\sum_{(x,y)\ne(i,j)}c_{x,y},\qquad s_{i,j}=\sum_{(x,y)\ne(i,j)}(s_{x,y}+c_{x,y}).$$

用二维前缀和可在 $O(1)$ 时间转移每个状态，得到 $O(nm)$ 算法。

组合公式

固定步数 $l$。先枚举 $x$ 坐标为正的步数并用插板法分配 $n$，再给 $y$ 坐标分配 $m$；交换求和顺序并使用 Vandermonde 恒等式，可化为只枚举 $i\le\min(n,m)$ 的公式：

$$\mathrm{Ans}(n,m)=\sum_{i=0}^{\min(n,m)} \binom ni\binom mi \left((i+2)2^s+s2^{s-1}\right), \quad s=n+m-i-1.$$

当 $s=0$ 时，第二项视为 $0$。预处理阶乘与逆阶乘即可 $O(1)$ 求组合数；循环中让 $2^s$ 每次乘 $2^{-1}$，无须保存幂数组。

单维特例

若 $n=1$，固定 $l$ 步时，唯一一次横坐标增量 $1$ 可放在 $l$ 个位置，纵坐标的方案数为 $\binom m{l-1}$。求和可得

$$\sum_{l=1}^{m+1}l(l+1)\binom m{l-1}=2^{m-2}(m^2+7m+8).$$

$m=1$ 时对称。该式构成独立的 $O(\log\max(n,m))$ 子任务算法。

复杂度

设 $N=\max(n,m)$。预处理复杂度为 $O(N)$，每组询问为 $O(\min(n,m))$；总空间复杂度为 $O(N)$。

子任务算法

• $n,m\le4$：递归枚举每一个下一顶点，直接累加所有完整路径的长度。
• $\min(n,m)=1$：使用单维闭式。
• $n,m\le2000$：使用二维前缀和 DP。
• 无限制：使用组合公式。