嘘月 题解

· · 题解

组合转换

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

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

  • p_t \leq 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}

注意到

&\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), 考虑

&\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}

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