组合转换

首先根据题意, 我们可以将问题表述成如下形式:

有多少 $n$ 阶排列 $q$, 满足: 存在互不相同位置 $p_m, p_{m+1}, \dots, p_{n-1}$, 使得 - $p_t \leq t$ - $q_{p_t}$ 递增?

正难则反, 问题本身的描述是从小到大选取的, 我们考虑从大到小选取.

以 $f(n, 0) = 1$ 为动态规划的起点, 其中 $f(i, j)$ 两个状态表示规划前 $i$ 个位置, 目前知道前 $i$ 个位置中有 $j$ 个数已经在 $t\geq i$ 的 $p_t$ 里被使用了.

那么在 $(i, j)$ 个位置, 我们要规划 $t=i-1$ 时候的选取, 我们只需贪心选取能选的最大值, 所以我们关心的其实是 $i$ 这个位置的数是否已经被选了. 1. 如果 $i$ 这个位置的数已经被选了, 我们有 $j$ 中可能之一. $(i, j)$ 以 $j$ 的权值转移到 $(i-1, j)$. 2. 否则 $i$ 这个位置的数没被选, 那么它是尚未被选的 $i-j$ 个数之一, 删掉它之后我们还需要再选一个数. $(i, j)$ 以 $i-j$ 的权值转移到 $(i-1, j+1)$.

值得注意的是, 这个 DP 的边界不是自然的! 最后我们询问 $m$ 的答案时, 要求和 $$ m!\cdot \sum_{i\leq m} f(m, i), $$ 但按照这个转移的话, $i > m$ 的地方也有值.

这就得到了一个 $O(n^2)$ 复杂度求所有答案的 DP.

代数变换

我们记 $f_i(x)$ 是第 $i$ 行的生成函数. 容易将 DP 的转移过程写成

$$ f_{i-1} = (x-x^2) f_i' + i x f_i. $$

注意到,

$$ \frac{f_{i-1}}{(1-x)^{i+1}} = x \left( \frac{f_i}{(1-x)^i} \right)', $$

所以令 $g_i(x) = f_i(x) / (1-x)^i$, 就有

$$ g_{i-1} = x(1-x)^2 g_i'. $$

再做换元 $h_n(u) = g_i(x)$, 其中 $u = te^t, t = x/(1-x)$, 可以验证

$$ h_{i-1} = u h_i'. $$

所以 $h_i$ 的变换就是直接把第 $k$ 次项系数乘以 $k$, 这是容易做的.

现在我们考虑如何提取答案. 记内积为 $\langle A(x), B(x) \rangle = \sum_n [x^n]A\cdot [x^n]B$, 我们希望求的是

$$ \begin{aligned} &\quad \langle f_i(x), 1 + x + \cdots + x^i \rangle\\ &= \left\langle g_i(x)(1-x)^i, 1 + x + \cdots + x^i \right\rangle, \end{aligned} $$

注意到 $$ \begin{aligned} &\quad \langle x^k (1-x)^i, 1 + x + \cdots + x^i \rangle\\ & = [x^i] x^k(1-x)^i \cdot \frac 1{1-x}\\ & = [x^{i-k}] (1-x)^{i-1} \\ & = [x^{k}] x(x-1)^{i-1}, \end{aligned} $$

可知前面的内积有

$$ \begin{aligned} &\quad \left\langle g_i(x)(1-x)^i, 1 + x + \cdots + x^i \right\rangle\\ &= \left\langle g_i(x), x(x-1)^{i-1} \right\rangle\\ &= \left\langle h_i(u), x(x-1)^{i-1} \right\rangle\\ &= \left\langle h_i(te^t), x(x-1)^{i-1} \right\rangle, \end{aligned} $$

由于 $t = x/(1-x)$, 考虑 $$ \begin{aligned} &\quad \langle t^k, x(x-1)^{i-1} \rangle\\ & = \left\langle \left(\frac{x}{1-x}\right)^k, x(x-1)^{i-1} \right\rangle\\ &= [x^i] \left(\frac{x}{1-x}\right)^k \cdot (1-x)^{i-1}\\ &= [x^i] x^k \cdot (1-x)^{i-1-k}\\ &= [i = k], \end{aligned} $$

所以 $$ \begin{aligned} &\quad \left\langle h_i(te^t), x(x-1)^{i-1}\right\rangle\\ &= \sum_{j\leq i} [u^j] h_i \cdot [t^i] (te^t)^j\\ &= \sum_{j} [u^j] h_i \cdot \frac{j^{i-j}}{(i-j)!}\\ &= \sum_{j} [u^j] h_n j^{n-i} \cdot \frac{j^{i-j}}{(i-j)!}\\ &= \sum_{j} [u^j] h_n \cdot \frac{j^{n-j}}{(i-j)!}\\ &= [T^i] \left( \sum_j ([u^j]h_n) \cdot j^{n-j} T^j \right) e^T. \end{aligned} $$

我们只要求出 $h_n(u)$ 的系数就做完了. 有 $$ \begin{aligned} g_n(x) &= \left(\frac 1{1-x}\right)^n\\ &= (1 + t)^n\\ &= \left( 1 + \sum_{k \geq 1} \frac{(-k)^{k-1}}{k!} u^k \right)^n, \end{aligned} $$

因此有多项式快速幂就可以了.