C++ 解法, 执行用时: 1517ms, 内存消耗: 10684K, 提交时间: 2022-04-15 20:19:25

//copied from https://loj.ac/s/511148
#include<cstdio>
const int maxn=500010,mod=998244353;
int n,f[maxn],fac[maxn],ifac[maxn];
char s[maxn];
int pw(int a,int n=mod-2){int b=1;for(;n;n>>=1)n&1?b=1ll*b*a%mod:1,a=1ll*a*a%mod;return b;}
int A[1<<19],B[1<<19],ws[1<<19];
void dft(int*a,int n,bool r=0){
	int*w=ws+n/2;*w=1;w[1]=pw(3,(mod-1)/n);
	if(r)w[1]=pw(w[1]);
	for(int i=2;i<n/2;i++)w[i]=1ll*w[i-1]*w[1]%mod;
	for(int i=n/2;--i;)ws[i]=ws[i*2];
	w=ws+1;
	for(int i=0,j=0,t;i<n;i++){
		if(i<j)t=a[i],a[i]=a[j],a[j]=t;
		for(t=n/2;(j^=t)<t;t/=2);
	}
	for(int i=1;i<n;w+=i,i*=2){
		for(int j=0;j<n;j+=i*2){
			for(int k=0,t;k<i;k++){
				t=1ll*a[j+i+k]*w[k]%mod;
				a[j+i+k]=(a[j+k]+mod-t)%mod;
				a[j+k]=(a[j+k]+t)%mod;
			}
		}
	}
	if(r){
		long long I=pw(n);
		for(int i=0;i<n;i++)a[i]=a[i]*I%mod;
	}
}
void solve(int l,int r){
	if(r-l==1)return;
	int mid=l+r>>1;
	solve(l,mid);
	int N=1;while(N<=(mid-l-1)+(r-l-1))N*=2;
	for(int i=0;i<N;i++)A[i]=l+i<mid?f[l+i]:0,B[i]=l+i<r?mod-ifac[i]:0;
	dft(A,N);dft(B,N);
	for(int i=0;i<N;i++)A[i]=1ll*A[i]*B[i]%mod;
	dft(A,N,1);
	for(int i=mid;i<r;i++)if(s[i-1]!='<')f[i]=(f[i]+A[i-l])%mod;
	solve(mid,r);
}
int nn,p[200002],pos[200002];
int main(){
	scanf("%d",&nn);
	for(int i=1;i<=nn;++i)scanf("%d",&p[i]),pos[p[i]]=i;
	for(int i=2;i<=nn;++i)if(pos[i]<pos[i-1])s[n++]='<';else s[n++]='>';
	for(int i=*fac=1;i<=n+1;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n+1]=pw(fac[n+1]);
	for(int i=n+1;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
	f[0]=1;
	solve(0,n+2);
	int ans=1ll*fac[n+1]*f[n+1]%mod;
	for(int i=0;i<=n;i++)if(s[i]!='<')ans=(mod-ans)%mod;
	printf("%d",ans);
}