人类没救了。

题解

对于排列 $p$，定义：

• 超越数 $\operatorname{exc}(p)=\#{i\mid p_i>i}$；
• 下降数 $\operatorname{des}(p)=\#{i\mid p_i>p_{i+1}}$。

题目要求统计 $\operatorname{exc}(p)=x$ 且 $\operatorname{des}(p)=y$ 的排列数量。

1. 建立生成函数

定义二元多项式 $A_n(s,t)=\sum_{p\in S_n}s^{\operatorname{des}(p)}t^{\operatorname{exc}(p)}$。

其中 $s$ 的指数记录下降数，$t$ 的指数记录超越数，因此答案就是 $\operatorname{ans}_{x,y}=[s^yt^x]A_n(s,t)$。

下降数和超越数的联合分布满足以下生成函数：

$$ \sum_{N\ge 0}\frac{A_N(s,t)}{(1-s)^{N+1}}u^N = \sum_{r\ge 0}s^r \frac{(1-t)(1-ut)^r} {(1-u)\bigl((1-u)^r-t(1-ut)^r\bigr)} $$

定义 $f_{r,x}$ 为 $\dfrac{A_n(s,t)}{(1-s)^{n+1}}$ 中 $s^rt^x$ 的系数，即

$$ f_{r,x} = [u^nt^x] \frac{(1-t)(1-ut)^r} {(1-u)\bigl((1-u)^r-t(1-ut)^r\bigr)} $$

接下来计算所有 $f_{r,x}$。

2. 展开生成函数

将分母按照等比数列展开：

$$ \frac{(1-t)(1-ut)^r} {(1-u)\bigl((1-u)^r-t(1-ut)^r\bigr)} = \sum_{k\ge 0} (t^k-t^{k+1}) (1-ut)^{r(k+1)} (1-u)^{-r(k+1)-1} $$

固定 $k$，令 $m=r(k+1)$。

由二项式定理，有 $(1-ut)^m=\sum_{j=0}^m(-1)^j\binom mj u^jt^j$；同时有 $(1-u)^{-m-1}=\sum_{q\ge 0}\binom{m+q}{q}u^q$。

因此，两者乘积中 $u^nt^j$ 的系数为 $(-1)^j\binom mj\binom{m+n-j}{n-j}$。

定义

$$ F(m,j)= \begin{cases} (-1)^j\binom mj\binom{m+n-j}{n-j},&0\le j\le\min(m,n),\\ 0,&\text{其他情况} \end{cases} $$

前面的 $t^k-t^{k+1}$ 会产生两部分贡献：

• $t^k$ 要从后面的乘积中取出 $t^{x-k}$；
• $-t^{k+1}$ 要从后面的乘积中取出 $t^{x-k-1}$。

所以

$$ f_{r,x} = \sum_{k=0}^x \left( F(r(k+1),x-k)-F(r(k+1),x-k-1) \right) $$

枚举 $r$、$x$ 和 $k$，即可求出所有 $f_{r,x}$。

3. 恢复原多项式

由 $f_{r,x}$ 的定义，有 $A_n(s,t)=(1-s)^{n+1}\sum_{r,x}f_{r,x}s^rt^x$。

又因为 $(1-s)^{n+1}=\sum_{j=0}^{n+1}(-1)^j\binom{n+1}{j}s^j$，所以 $A_n(s,t)$ 中 $s^yt^x$ 的系数为

$$ \operatorname{ans}_{x,y} = \sum_{r=0}^y (-1)^{y-r} \binom{n+1}{y-r} f_{r,x} $$

这正是超越数为 $x$、下降数为 $y$ 的排列数量。

输出时，第 $x+1$ 行、第 $y+1$ 个数输出 $\operatorname{ans}_{x,y}$。

4. 组合数预处理

计算 $F(m,j)$ 时，$m=r(k+1)$，因此 $m=O(n^2)$，组合数的最大上标也是 $O(n^2)$，但下标最多只有 $n+1$。

虽然模数 $M$ 是质数，但可能有 $M\le n^2$，所以不能直接使用阶乘和逆元计算组合数。

使用 Pascal 递推即可：$\binom i0=1$，$\binom ij=\binom{i-1}j+\binom{i-1}{j-1}\pmod M$。

预处理上标不超过 $n^2+n$、下标不超过 $n+1$ 的组合数即可。

复杂度分析

组合数预处理需要 $O(n^3)$ 时间。

计算所有 $f_{r,x}$ 需要枚举 $r$、$x$ 和 $k$，时间复杂度为 $O(n^3)$。

恢复所有答案的时间复杂度同样为 $O(n^3)$。

因此总时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^3)$。