官方题解只能做到 $O(K^4 + K^2(N + M))$？玩的太差了。这题可以做到确定性的 $\widetilde O(N+M+K+d^2)$，其中 $d=\min(K-1,h-1)$，$h=\min(R,C)+\min(N-R,M-C)$ 是经过目标格子的左上—右下对角线长度。这里 $\widetilde O$ 隐去对数因子；后面会给出更精确的复杂度，以及真正达到该复杂度的 C++ 实现。

题目要求统计行、列均不降，元素属于 $[1,K]$，且 $a_{R,C}=V$ 的矩阵，答案模 $998244353$。约束为 $N,M\le 200$、$K\le 100$。

直接对 LGV 行列式插值，需要 $O(K^4+K^2(N+M))$；将线性矩阵多项式转成特征多项式，可以降到 $O(K^2(N+M+K))$，QOJ 上已有题解提到了这一步。进一步优化的关键不是继续优化普通矩阵运算，而是把行列式改写成 Hankel 结构。([QOJ][2])

从不相交路径到一维点集

令 $k=K-1$。对每个阈值 $i+1$，画出元素不超过 $i+1$ 的区域的右下边界，其中 $0\le i< k$。这些边界都是从 $(N,0)$ 到 $(0,M)$、只向上或向右走的路径。把第 $i$ 条路径平移 $(i,i)$，就得到了从 $A_i=(N+i,i)$ 到 $B_i=(i,M+i)$ 的 $k$ 条点不相交路径。这个轮廓线模型也是已有题解的出发点。([QOJ][3])

以下坐标的第一维向下、第二维向右。记 $\delta=R-C$，用直线 $x-y=\delta$ 切开所有路径。每走一步，$x-y$ 都恰好减少 $1$，因此每条路径与这条直线恰好相交一次。

设 $s=\min(R,C)$、$h=s+\min(N-R,M-C)$、$W=k+h$。这条切线上可能被经过的点，可以依次编号为 $0,1,\ldots,W-1$，编号 $t$ 对应坐标 $(\max(0,\delta)+t,\max(0,\delta)+t-\delta)$。

于是，一个路径族在切线上的交点构成一个大小为 $k$ 的集合 $T$。

令 $q=s+V-2$。原来的限制 $a_{R,C}=V$，恰好等价于：

编号 $q$ 不被经过，而且 $T$ 中恰好有 $V-1$ 个编号小于 $q$。

原因是：阈值 $V-1$ 的边界必须在目标格子的左上方，阈值 $V$ 的边界必须在目标格子的右下方。平移后，这两条路径分别位于点 $(R+V-2,C+V-2)$ 的两侧，而这个点正是编号 $q$。当 $V=1$ 或 $V=K$ 时，其中一侧没有对应路径，结论仍然成立。

现在计算固定交点集合 $T$ 的方案数。

切线前、后的路径长度分别为 $L=N-\delta$、$H=M+\delta$。两部分分别应用 LGV，得到两个二项式行列式。这里使用恒等式 $\det\bigl(\binom{L}{u_j-i}\bigr)*{0\le i,j< k} =\Delta(u)\prod*{i=0}^{k-1}(L+i)!/\prod_{j=0}^{k-1}\bigl(u_j!(L+k-1-u_j)!\bigr)$， 其中 $\Delta(u)=\prod_{i< j}(u_j-u_i)$。

这个恒等式并不难证明：每列提出分母后，各行成为关于 $u_j$ 的次数不超过 $k-1$ 的多项式，因此行列式是 Vandermonde 行列式的常数倍；代入 $u_j=j$，原二项式矩阵为对角线全是 $1$ 的上三角矩阵，就能确定常数。

记 $\alpha=|\delta|$、$\beta=|N-M-\delta|$，并定义 $\Gamma=\prod_{i=0}^{k-1}(N-\delta+i)!(M+\delta+i)!$、 $w_t=\bigl(t!(t+\alpha)!(W-1-t)!(W-1-t+\beta)!\bigr)^{-1}$。 将切线两侧的行列式相乘，便得到：

$$ \#\{\text{交点集合为 }T\text{ 的路径族}\} = \Gamma\,\Delta(T)^2\prod_{t\in T}w_t. $$

所有逆元都在模 $998244353$ 下计算。题目范围内涉及的阶乘参数远小于模数，因此这些阶乘均可逆。

到这里，二维路径计数已经变成了一维加权点集计数。不过，还可以通过取补集，把点集大小从 $k$ 缩到 $h-1$。

设 $U={0,\ldots,W-1}$，$J=U\setminus T$，则 $|J|=h$。定义 $\overline w_t=\dfrac{(t+\alpha)!(W-1-t+\beta)!}{t!(W-1-t)!}$， 以及 $\Gamma_*=\Gamma\prod_{t=0}^{W-1}\bigl((t+\alpha)!(t+\beta)!\bigr)^{-1}$。 有 $\Gamma\Delta(T)^2\prod_{t\in T}w_t =\Gamma_*\Delta(J)^2\prod_{t\in J}\overline w_t$。

这个等式可以直接拆分整个集合 $U$ 的 Vandermonde 乘积证明。用到的两个关系是 $\Delta(U)=\prod_{t=0}^{W-1}t!$，以及 $\prod_{u\in U,u\ne t}(t-u)=(-1)^{W-1-t}t!(W-1-t)!$；平方后符号消失。

原限制要求 $q\notin T$，因此 $q\in J$；而 $J$ 中小于 $q$ 的元素个数为 $q-(V-1)=s-1$。把必选的 $q$ 从 $J$ 中删掉，它与其余点之间的 Vandermonde 因子，可以吸收到点权中：令 $\omega_t=(t-q)^2\overline w_t$，剩余的点集大小就只有 $h-1$。

因此，选择下面两种表示中阶数较小的一种即可。

若 $k\le h-1$，取 $d=k$、目标次数 $e=V-1$、常数因子 $c=\Gamma$，点权为 $\omega_t=w_t$，但令 $\omega_q=0$。

否则取 $d=h-1$、$e=s-1$、$c=\Gamma_*\overline w_q$，点权为 $\omega_t=(t-q)^2\overline w_t$。此时自然有 $\omega_q=0$。

两种表示统一成：选出 $d$ 个点，其中恰有 $e$ 个小于 $q$，每个集合的权值为 Vandermonde 平方乘各点权，最后乘上 $c$。如果 $d=0$，答案直接为 $c$。

利用 Hankel 结构近二次地提取系数

定义两组矩 $A_j=\sum_{t< q}\omega_t t^j$、 $B_j=\sum_{t>q}\omega_t t^j$， 只需要计算 $0\le j\le 2d-2$。

对 Vandermonde 矩阵使用 Cauchy–Binet 公式，得到：

$$ F(x)=\det\bigl(B_{i+j}+xA_{i+j}\bigr)_{0\le i,j< d}, \qquad \mathrm{Ans}=c\,[x^e]F(x). $$

展开后，每个大小为 $d$ 的点集贡献一次，两个 Vandermonde 行列式相乘得到 $\Delta(T)^2$，而每个小于 $q$ 的点额外贡献一个 $x$。这里按集合求和，不需要额外乘除 $d!$。

这个矩阵的元素只依赖 $i+j$，所以是 Hankel 矩阵。整个矩阵实际上只有 $2d-1$ 个不同的元素。

先处理矩的计算。不要逐个枚举点和幂次，而是利用生成函数 $\sum_{j\ge0}A_jz^j=\sum_{t< q}\dfrac{\omega_t}{1-tz}$， $B_j$ 同理。分治合并这些分式，每次使用 $\dfrac{P_1}{Q_1}+\dfrac{P_2}{Q_2}=\dfrac{P_1Q_2+P_2Q_1}{Q_1Q_2}$， 并始终截断到 $z^{2d-1}$。最后做一次多项式求逆，就得到了全部需要的矩。这部分复杂度为 $O(W\log^2(d+1))$。

接下来，对于一个给定的 $x$，需要计算数值 Hankel 行列式。这一步可以通过半 GCD 在 $O(d\log^2(d+1))$ 内完成，不需要高斯消元，也不要求各阶顺序主子式非零。这一快速 Hankel 行列式算法可以由 Hankel 连分式与多项式欧几里得算法之间的关系得到。([arXiv][4])

具体地，给定矩序列 $\mu_0,\ldots,\mu_{2d-2}$，构造 $f_0(z)=z^{2d-1}$、 $f_1(z)=\sum_{j=0}^{2d-2}\mu_jz^{2d-2-j}$。 进行带负余数的多项式欧几里得算法：$f_{i+2}=Q_if_{i+1}-f_i$。对每个商，只记录其次数 $m_i$ 和最高次项系数 $b_i$。

设当前累计次数为 $r$，已知 $r$ 阶 Hankel 行列式为 $D$，并维护 $P=\prod_{\text{已经处理的 }i}b_i^2$。初始为 $r=0$、$D=1$、$P=1$。处理下一对 $(m,b)$ 时，递推为：

$$ D\leftarrow (-1)^{m(m-1)/2}D\,(bP)^{-m}, \qquad P\leftarrow Pb^2, \qquad r\leftarrow r+m. $$

被累计次数跳过的那些阶数，其 Hankel 行列式全部为零。因此，如果累计次数从小于 $d$ 跳到了大于 $d$，答案就是零；若欧几里得算法提前终止，也返回零。这个公式正好覆盖模意义下的各种奇异情况，不能把每次商的次数都假设成 $1$。([arXiv][5])

普通欧几里得算法仍可能花费二次时间。代码用半 GCD 批量得到这些商的信息，通过多项式乘法维护变换矩阵，使单次 Hankel 行列式计算达到 $O(d\log^2(d+1))$。实现中的 hankel_det 没有奇异时退回高斯消元的分支，因而复杂度保证不依赖非退化假设。

最后处理插值。还可以减少需要计算的点值数量。

左侧有 $q$ 个可选点，右侧有 $W-1-q$ 个。选出 $d$ 个点时，左侧点数必然介于 $\ell=\max(0,d-(W-1-q))$ 与 $u=\min(d,q)$ 之间。所以 $F(x)=x^\ell G(x)$，其中 $\deg G\le u-\ell$。

因为已经选择了 $d=\min(k,h-1)$，有 $W-1\ge2d$，从而 $u-\ell=\rho=\min(d,q,W-1-q)$。

取严格大于 $\rho$ 的最小二次幂 $E$，在 $E$ 次单位根处计算 $F(x)x^{-\ell}$，再做一次逆 NTT，就能得到 $G$ 的系数。所有求值点都非零，不存在除以零的问题。答案是 $c[x^{e-\ell}]G(x)$。

令 $S=N+M+K$。阶乘预处理为 $O(S)$，矩的计算为 $O(W\log^2(d+1))$，需要求 $O(\rho+1)$ 次 Hankel 行列式，因此精确的时间复杂度为：

$$ O\left(S+\bigl(W+(\rho+1)d\bigr)\log^2(d+1)\right), \qquad d=\min(K-1,h-1),\quad \rho=\min(d,q,W-1-q). $$

最坏情况下为 $\widetilde O(S+d^2)$，空间复杂度为 $O(S)$。当 $d=0$ 时，只需要 $O(S)$ 时间。这里给出的是一个确定性算法上界，并不将它误称为已经证明的全局最优下界。