qoj7759

令 A(n,x,y)A(n, x, y) 表示长度为 nn 的排列中，有 xx 个上升的连续对，且它的逆排列有 yy 个上升的连续对的排列数量。

根据组合恒等式，我们有如下关系：

(uv+n−1n)=∑x=0n−1∑y=0n−1A(n,x,y)(u+xn)(v+yn) \binom{uv + n - 1}{n} = \sum_{x=0}^{n-1} \sum_{y=0}^{n-1} A(n, x, y) \binom{u+x}{n} \binom{v+y}{n}

我们考虑反解出 A(n,x,y)A(n, x, y)。

令 x′=n−x,y′=n−yx' = n - x, y' = n - y，并代入整数 u=i,v=ju=i, v=j (1≤i,j≤n1 \le i, j \le n)，我们可以构建一个线性方程组。

定义矩阵 L,C,AL, C, \mathcal{A} 如下：

  • Lij=(ij+n−1n)L_{ij} = \binom{ij + n - 1}{n}，其中 1≤i,j≤n1 \le i, j \le n。
  • Cik=(n+i−kn)C_{ik} = \binom{n + i - k}{n}，其中 1≤i,k≤n1 \le i, k \le n。
  • Ax′y′=A(n,n−x′,n−y′)\mathcal{A}_{x'y'} = A(n, n-x', n-y')。

上述恒等式可以表示如下形式：

L=C⋅A⋅CT L = C \cdot \mathcal{A} \cdot C^T

我们的目标是求 A\mathcal{A}，因此有：

A=C−1⋅L⋅(CT)−1=C−1⋅L⋅(C−1)T \mathcal{A} = C^{-1} \cdot L \cdot (C^T)^{-1} = C^{-1} \cdot L \cdot (C^{-1})^T

矩阵 CC 是一个下三角矩阵，其逆矩阵 C−1C^{-1} 有显式的封闭形式：

(C−1)ij=(−1)i−j(n+1i−j) (C^{-1})_{ij} = (-1)^{i-j} \binom{n+1}{i-j}

（当 i<ji < j 时为 0）。