菜王的 blog

有点东西。下面令 $k$ 表示题面中的 $n - k$。

考虑用图结构刻画操作。对于最终的删除序列，考虑将 $n - j + 1$ 向 $b_j$ 连边。由于每个点入度与出度都 $\le 1$，这样连出来的图形如若干个环与 $k$ 条有向链，这些链的终点分别为点 $1, 2, \dots, k$。而最后剩下的序列 $a$ 满足 $a_i$ 为终点是点 $i$ 的那条链的起点的编号。

这样做实际上是将序列中值的替换关系用链结构表示出来，而一个环就代表了一个在序列末被直接删掉的数。

现在考虑计数。考虑一件事情：如果点 $1, 2, \dots, k$ 都有入度，我们可以随意交换它们之间的入边。也就是说，对于所有点 $1, 2, \dots, k$ 都有入度的图来说，满足 $a$ 递增的恰好占其中的 $\frac 1{k!}$。但是如果这些点并不是都有入度，这样的映射就不成立了。而有入度的点肯定会是一段后缀，假设有 $i$ 个点有入度，那么可以类似的推出，满足 $a$ 递增的恰好占其中的 $\frac 1{i!}$。

对于一个 $i$ 而言，我们在后面 $n - k$ 个点中选出 $i$ 个点向前面有入度的点分别连边，剩下 $n - k - i$ 个点随意连边，方案数为：

$\binom{n - k}i i! (n - k)^{\underline{n - k - i}}$

然后还要在此基础上除掉一个 $i!$，因为我们要求的是满足 $a$ 递增的方案。化简后得到最终答案为：

$\sum_{i = 0}^k \binom{n - k}i^2 (n - k - i)!$

可以预处理后单次 $\mathcal{O}(k)$ 回答询问。