====== Atcoder Rugular Contest 112 ======

[[https://atcoder.jp/contests/arc112|比赛链接]]

===== E - Cigar Box =====

==== 题意 ====

给定初始序列 $(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$ 统计贡献即可。

<hidden 查看代码>
<code cpp>
const int MAXN=3005,Mod=998244353;
int C[MAXN][MAXN],dp[MAXN][MAXN],a[MAXN];
int main()
{
	int n=read_int(),m=read_int();
	_rep(i,1,n)a[i]=read_int();
	C[0][0]=1;
	_rep(i,1,n){
		C[i][0]=1;
		_rep(j,1,i)
		C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
	}
	dp[0][0]=1;
	_rep(i,1,n){
		int s=0;
		_rep(j,0,m){
			s=(2LL*i*s+dp[i-1][j])%Mod;
			dp[i][j]=s;
		}
	}
	int ans=0;
	_rep(i,0,n){
		for(int j=n-i;j>=0;j--){
			if(n-i-j>=2&&a[n-j]<a[n-j-1])break;
			if(m-i-j>=0)ans=(ans+1LL*dp[i+j][m-i-j]*C[i+j][i])%Mod;
		}
	}
	enter(ans);
	return 0;
}
</code>
</hidden>