题解：P13969 [VKOSHP 2024] Exchange and Deletion

题面：

我们考虑从图论意义计数，把 swap 改成连边，由于交换完前面的点直接被删了，所以只保留从后向前的连边。

那么最后连到 \(n-k\) 前的点的数值等于链头，而 \(n-k\) 后的点和链上非链头的点实际上都被删了。手玩一下，发现后面 \(k\) 个点都是向前连一条边（或向自己）。

为了保证递增，可以发现合法从后面来的点都是递增排在 \([1,n-k]\) 后缀的。
那么枚举 \(i\) 表示链尾成功到达 \([1,n-k]\) 的链个数。

\(ans=\sum_{i=0}^{min(k,n-k)} C_{k}^ik^{ \frac{k-i}{} }\)

解释：从后面 \(k\) 个点选择 \(i\) 个点越过 \(n-k\) 点，后面 \(k-i\) 个点肯定在 \([n-k+1,n]\) 内随便找个点连（向前连），同时注意我们不能钦定多于 \(n-k\) 个点到 \([1,n-k]\)。

下降幂不好处理可以化式子：

\(ans=\sum_{i=0}^{min(k,n-k)}(C_k^i)^2(k-i)!\)