123
A
LGV引理，\(n\times m\)矩阵左下右上为 1 的方案数为
\[ f(n,m)= \det\begin{pmatrix} \binom{n+m-2}{n-1} & \binom{n+m-2}{n} \\ \binom{n+m-2}{m} & \binom{n+m-2}{m - 1} \end{pmatrix}= \frac{(n+m-2)!(n+m-1)!}{n!m!(n-1)!(m-1)!} \]
分 4 类求和：
- \(a=n,b=m\)：\(f(a,b)\)
- \(a=n,b<m\)：\(\sum f(n,b)(m-b+1)\)
- \(a<n,b=m\)：\(\sum f(a,m)(n-a+1)\)
- \(a<n,b<m\)：\(2\sum f(a,b)\)，放在左下右上共 2 种方案，该式可以卷积优化 \[ \sum_s(s-2)!(s-1)!\sum_{a,b,a+b=s}\frac{1}{a!(a-1)!}\cdot\frac{1}{b!(b-1)!} \]
故总时间复杂度 \(O((n+m)\log(n+m))\)。