#C231028B. 排列(per)

前言（Front talk)

开始补之前的题。

网址（Website）

题目详情 - 排列(per) - Super

题解 - 排列(per) - Super

题目（Problem）

给定一个长度为的排列。小会进行以下操作次:

将当前序列的最小值加入序列末尾。
从序列的开头或者末尾删去一个数。

小想知道能得到几种不同的序列, 请你帮帮他。输出答案对取模后的结果。

对于的数据,。

题解（Solution）

这道题会出现严重的读题错误（bushi），我直接把它的一个操作的两个步骤看成了一个操作选任意一个操作，现在补题的时候才发现。

按题解来说，考虑一件事情：如果对于当前区间中有最小值，那么要想使中出现，就必须将的所有数全部删去，而若在删左边的过程中删除了右边的数，则会增加在中出现的次数。想要使出现也是一个道理。如果想让后边只有出现，那么需要删掉左右两边的所有数。

于是乎，这道题就转化为一道题：设表示当前区间中区间最小值为，且满足的最后一个元素在区间外 ，。前缀和优化后可以做到。

而我最大的问题就是难以对这类题目求出方程。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
const int mod = 998244353;
const int N = 5005;
pair<int,int> mn[N][24];
int n,a[N];
int dp[N][N],sl[N][N],sr[N][N];
inline pair<int,int> ask(int l,int r){
	int k=__lg(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}

inline void trans(int l,int r){
	int minn=ask(l,r).second;
	dp[l][r]=(1ll*sl[minn+1][r]+sr[l][minn-1]+1)%mod;
	sl[l][r]=(1ll*sl[l][r-1]+dp[l][r])%mod;
	sr[l][r]=(1ll*sr[l+1][r]+dp[l][r])%mod;
}

signed main(){
	freopen("per.in","r",stdin);
	freopen("per.out","w",stdout); 
	n=input();For(i,1,n) a[i]=input(),mn[i][0]={a[i],i};
	for(int j=1;j<=18;j++)//预处理 ST 表 
		for(int i=1;i+(1<<j)-1<=n;i++)
			mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
	Rof(i,n,1) For(j,i,n) trans(i,j);
	return printf("%lld",dp[1][n]),0;
}