C++(clang++11) 解法, 执行用时: 2253ms, 内存消耗: 55056K, 提交时间: 2020-11-28 20:34:25

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid (l+r>>1)
#define pb push_back

using namespace std;
const int N=50005,mod=998244353;
typedef long long LL;
int n,a[2][N<<1],len,bin[N<<2];
LL ans,A[N<<2],B[N<<2],Wn[19][1<<19];
vector <LL> tmp[2][2],vt[2][2][N<<1];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

LL getmi(LL a,LL x)
{
	LL rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

void FFT(LL a[],int len,int tp)
{
	rep(i,0,len-1) bin[i]=bin[i>>1]>>1|((i&1)*(len>>1));
	rep(i,0,len-1) if(i<bin[i]) swap(a[i],a[bin[i]]);
	for(int i=1,cnt=0; i<len; ++cnt,i<<=1)
	{
		for(int j=0; j<len; j+=i<<1)
		{
			LL w=0,x,y;
			rep(k,0,i-1)
			{
				x=a[j+k],y=a[i+j+k]*Wn[cnt][w+i],w+=tp;
				a[j+k]=(x+y)%mod,a[i+j+k]=(x-y)%mod;
			}
		}
	}
	if(tp==-1)
	{
		LL x=getmi(len,mod-2);
		rep(i,0,len-1) a[i]=a[i]*x%mod;
	}
}

void inc(LL &x,LL y)
{
	if((x+=y)>=mod) x-=mod;
}

void mul(vector <LL> &a,vector <LL> &b,vector <LL> &c)
{
	int sz1=b.size()-1;
	int sz2=c.size()-1;
	for(len=1; len<=sz1+sz2; len<<=1);
	rep(i,0,len-1) A[i]=B[i]=0;
	rep(i,0,sz1) A[i]=b[i];
	rep(i,0,sz2) B[i]=c[i];
	FFT(A,len,1),FFT(B,len,1);
	rep(i,0,len-1) A[i]=A[i]*B[i]%mod;
	FFT(A,len,-1);
	int sz=a.size()-1;
	rep(i,0,min(n,sz1+sz2))
	{
		if(i<=sz) inc(a[i],A[i]);
		else a.pb(A[i]);
	}
}

void solve(int l,int r)
{
	if(l==r)
	{
		rep(i,0,1) rep(j,0,1) vt[i][j][l].clear();
		vt[1][1][l].pb(0),vt[1][1][l].pb(1),vt[0][0][l].pb(1);
		return;
	}
	solve(l,mid),solve(mid+1,r);
	rep(i,0,1) rep(j,0,1) tmp[i][j].clear();
	rep(i,0,1) rep(j,0,1) rep(_i,0,1) rep(_j,0,1) if(a[j][mid]<=a[_i][mid+1])
		mul(tmp[i][_j],vt[i][j][l],vt[_i][_j][mid+1]);
	rep(i,0,1) rep(j,0,1) vt[i][j][l]=tmp[i][j];
}	

LL query(vector <LL> &a,int x)
{
	int sz=a.size()-1;
	if(x<=sz) return a[x];
	return 0;
}

int main()
{
	n=getint();
	rep(i,1,2*n) a[1][i]=getint();
	rep(i,1,2*n) a[0][i]=getint();
	rep(i,0,18)
	{
		int x=1<<i;
		Wn[i][x]=1;
		LL wn=getmi(3,(mod-1)/(x<<1));
		rep(j,1,x-1) Wn[i][j+x]=Wn[i][j+x-1]*wn%mod;
		wn=getmi(wn,mod-2);
		rep(j,1,x-1) Wn[i][-j+x]=Wn[i][-j+x+1]*wn%mod;
	}
	solve(1,2*n);
	rep(i,0,1) rep(j,0,1) ans=(ans+query(vt[i][j][1],n))%mod;
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}