给定初始序列 $(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}$ 单增即可计入贡献。
最后问题就剩下计算每个 $\prod_{i=1}^{l+r}(2i)^{c_i}$ 了,设 $\text{dp}(i,j)=\prod_{k=1}^{i}(2k)^{c_k}\left(\sum_{k=1}^{i}{c_k}=j\right)$,考虑枚举 $c_i$,于是有状态转移:
$$ \text{dp}(i,j)=\sum_{k=0}^j (2i)^{j-k}\text{dp}(i-1,k) $$
记录一下前缀和,即可 $O(nm)$ 完成 $\text{dp}$,最后 $O(n^2)$ 枚举 $l,r$ 统计贡献即可。