AT_arc112_e

唐龙题不知道为什么有 2600。此处应有[对称唐龙.gif]。

首先，把 $a_i=i$ 的序列 $a$ 变成给定序列显然是难做的，考虑将目标序列进行某种映射，转化成将 $a$ 变成 $a_i=i$。

然后发现，对于每个数字，只有对其的最后一次操作是有用的，并且进行放到开头的操作的数字一定是某个 $[1,i]$ 内的所有数，并且依次进行 $i,i-1,i-2,\cdots,1$ 的操作。放到末尾的同理。

于是考虑倒推每次操作，就变成了依次对 $1,2,\cdots,x$ 操作。并且对 $i$ 进行操作后，以后可以任意对 $i$ 操作。

则可以进行 dp：设 $dp_{i,j,k}$ 表示当前到第 $i$ 次操作，已经进行过放到第一的操作的为 $[1,j]$，进行过放到末尾的为 $[k,n]$ 的方案数。则转移为：$dp_{i,j,k}=dp_{i-1,j-1,k}+dp_{i-1,j,k+1}+(j+n-k+1)dp_{i-1,j,k}$。而对于没有进行过操作的数，它们之间的相对位置不变，则检查它们的相对位置是否符合条件即可。

这是 $O(n^3)$ 的。考虑优化状态。发现 $j$ 和 $k$ 无关，于是考虑记录 $[1,j]$ 和 $[k,n]$ 这些一共选了多少个，最后在乘上 $\binom{j+n-k+1}{j}$。状态为 $dp_{i,j}$ 表示前 $i$ 次操作，已经进行过操作的位置有 $j$ 个，则有转移：$dp_{i,j}=dp_{i-1,j-1}+2jdp_{i-1,j}$。

最后枚举 $j,k$，判断 $[j+1,k-1]$ 是否符合条件，再乘上上述组合数，全部情况相加即可。时间复杂度 $O(n^2)$。

code：

int n,m,a[N],p[N],dp[N][N],C[N][N];
bool pd[N][N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void Yorushika(){
	read(n,m);
	rep(i,1,n){
		read(p[i]);
		a[p[i]]=i;
	}
	dp[0][0]=1;
	rep(i,1,m){
		rep(j,1,n){
			dp[i][j]=Mod(dp[i-1][j-1],2ll*dp[i-1][j]*j%mod);
		}
	}
	pd[1][0]=1;
	rep(i,1,n){
		pd[i][i]=pd[i+1][i]=1;
		rep(j,i+1,n){
			if(p[j]<p[j-1]){
				break;
			}
			pd[i][j]=1;
		}
	}
	C[0][0]=1;
	rep(i,1,n){
		C[i][0]=C[i][i]=1;
		rep(j,1,i-1){
			C[i][j]=Mod(C[i-1][j],C[i-1][j-1]);
		}
	}
	int ans=0;
	rep(i,0,n){
		rep(j,i+1,n+1){
			if(!pd[i+1][j-1]){
				continue;
			}
			ans=Mod(ans,1ll*dp[m][i+n-j+1]*C[i+n-j+1][i]%mod);
		}
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}