QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#384#89783#21750. 【PR #8】消愁SixNukesyyyyxhFailed.2023-09-29 16:51:312023-09-29 16:51:32

Details

Extra Test:

Invalid Input

input:

114

output:


result:

FAIL Integer parameter [name=n] equals to 114, violates the range [1, 100] (stdin, line 1)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89783#21750. 【PR #8】消愁yyyyxh100 ✓1ms1876kbC++141.3kb2023-03-21 11:20:172023-03-21 11:20:18

answer

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=103,P=998244353;
typedef long long ll;
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
int n,m,num;
int per[N],p[N];
int pos[N],a[N];
int f[N][N];
int fac[N],sm[N];
int C[N][N];
int used[N],pre[N];
int main(){
	n=read();
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%P;
	for(int i=1;i<=n;++i) per[i]=read();
	for(int i=1;i<=n;++i) p[per[i]]=read();
	for(int i=1;i<=n;++i) if(p[i]) pos[++m]=i,used[a[m]=p[i]]=1;
	for(int i=1;i<=n;++i){
		pre[i]=pre[i-1];
		if(!used[i]) ++pre[i];
	}
	pos[++m]=n+1;a[m]=n+1;f[0][0]=1;
	for(int i=0;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			inc(C[i][j]=C[i-1][j],C[i-1][j-1]);
	}
	for(int i=1;i<=m;++i)
		for(int j=0;j<i;++j)
			if(a[j]<a[i]){
				for(int k=0;k<=sm[j];++k){
					int dis=pos[i]-pos[j]-(i-j);
					int vdis=pre[a[i]-1]-pre[a[j]];
					int lm=min(dis,vdis);
					sm[i]=max(sm[i],sm[j]+lm);
					for(int x=0;x<=lm;++x)
						inc(f[i][k+x],(ll)C[dis][x]*C[vdis][x]%P*f[j][k]%P);
				}
			}
	int res=0;
	for(int i=0;i<=pre[n];++i) inc(res,(ll)f[m][i]*fac[pre[n]-i]%P);
	printf("%d\n",res);
	return 0;
}