比赛链接

给定初始序列 $(1,2\cdots n)$，每次操作可以任选一个数将其移动到序列最左边或最右边。

问恰好 $m$ 次操作将序列变成 $(a_1,a_2\cdots a_n)$ 的方案数。

首先最后一次操作一定是将 $a_1$ 移动到最左边，或者将 $a_n$ 移动到最右边。

假设最后先进行 $c_1(c_1\ge 0)$ 次操作都是对 $a_n$ 的操作然后再将 $a_n$ 移到最右边，于是这 $c_1$ 次操作有 $2^{c_1}$ 种方案。

于是问题转化为求 $(1,2\cdots n)$ 删去 $a_n$ 后恰好在 $m-c_1-1$ 次操作将序列变成 $(a_1,a_2\cdots a_{n-1})$ 的方案数。

假设问题转化后最后先进行 $c_2(c_2\ge 0)$ 次操作都是对 $a_{n-1}$ 或 $a_{n}$ 的操作然后再将 $a_{n-1}$ 移到最右边，于是这 $c_2$ 次操作有 $4^{c_2}$ 种方案。

更加形式的，假设所有操作删去的数为 $a_1,a_2\cdots a_l$ 以及 $a_{n-r+1},a_{n-r+2}\cdots a_n$，且假设删去的顺序固定，于是方案数为 $\prod_{i=1}^{l+r}(2i)^{c_i}$。

同时 $\sum_{i=1}^{l+r} c_i=m-l-r$，由于删去的顺序其实是不固定的，于是最终算贡献时需要乘上 ${l+r\choose l}$。

关于方案的合法性，$(1,2\cdots n)$ 删去 $a_1,a_2\cdots a_l$ 以及 $a_{n-r+1},a_{n-r+2}\cdots a_n$ 的数都未经操作。

于是剩下的排列就是 $(a_{l+1},a_{l+2}\cdots a_{n-r})$，所以只要 $a_{l+1},a_{l+2}\cdots a_{n-r}$ 单增即可计入贡献。