提出 #57135103

---

ソースコード 拡げる

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
const int P=998244353;
int ad(int k1,int k2){return k1+k2>=P?k1+k2-P:k1+k2;}
int su(int k1,int k2){return k1-k2<0?k1-k2+P:k1-k2;}
int mu(int k1,int k2){return 1ULL*k1*k2%P;}
void uad(int&k1,int k2){(k1+=k2)>=P&&(k1-=P);}
void usu(int&k1,int k2){(k1-=k2)<0&&(k1+=P);}
template<class... T>int ad(int k1,T... k2){return ad(k1,ad(k2...));}
template<class... T>int su(int k1,T... k2){return su(k1,ad(k2...));}
template<class... T>int mu(int k1,T... k2){return mu(k1,mu(k2...));}
template<class... T>void uad(int&k1,T... k2){return uad(k1,ad(k2...));}
template<class... T>void usu(int&k1,T... k2){return usu(k1,ad(k2...));}
int po(int k1,int k2){
	int k3=1;
	for(;k2;k2>>=1,k1=mu(k1,k1))if(k2&1)k3=mu(k3,k1);
	return k3;
}
using LL=long long;
using ULL=unsigned long long;
const int N=250005,K=20,M=250005;
int n,m,fa[N],a[M],b[M],lg[M],id[M],fac[M],ifac[M];
vector<int>e[N];
int tin[N],tou[N],idx;
int f[N][K],g[N][K];
int L[M],R[M];
void dfs(int k1){
	tin[k1]=++idx;
	for(auto&x:e[k1]){
		dfs(x);
	}
	tou[k1]=idx;
}
int qmin(int l,int r){
	int x=lg[r-l+1];
	return min(f[l][x],f[r-(1<<x)+1][x]);
}
int qmax(int l,int r){
	int x=lg[r-l+1];
	return max(g[l][x],g[r-(1<<x)+1][x]);
}
int tr[M];
void add(int x,int y){for(int i=x;i<M;i+=i&-i)tr[i]+=y;}
int query(int x){int y=0;for(int i=x;i;i&=i-1)y+=tr[i];return y;}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	fac[0]=1;
	rep(i,1,M-1)fac[i]=mu(fac[i-1],i);
	ifac[M-1]=po(fac[M-1],P-2);
	per(i,M-1,1)ifac[i-1]=mu(ifac[i],i);
	rep(i,2,M-1)lg[i]=lg[i>>1]+1;
	rd(n),rd(m);
	rep(i,2,n)rd(fa[i]),e[fa[i]].pb(i);
	dfs(1);
	rep(i,1,m)rd(a[i]);
	rep(i,1,m)rd(b[i]);
	rep(i,1,m){
		f[i][0]=tin[b[i]];
		g[i][0]=tin[b[i]];
	}
	rep(j,1,K-1)rep(i,1,m-(1<<j)+1){
		f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		g[i][j]=max(g[i][j-1],g[i+(1<<(j-1))][j-1]);
	}
	rep(i,1,m){
		L[i]=R[i]=i;
		per(j,K-1,0)if(L[i]-(1<<j)>=1&&tin[a[i]]<=qmin(L[i]-(1<<j),i)&&qmax(L[i]-(1<<j),i)<=tou[a[i]]){
			L[i]-=1<<j;
		}
		per(j,K-1,0)if(R[i]+(1<<j)<=m&&tin[a[i]]<=qmin(i,R[i]+(1<<j))&&qmax(i,R[i]+(1<<j))<=tou[a[i]]){
			R[i]+=1<<j;
		}
	}
	int lst=0;
	auto push=[&](int cur){
		rep(i,lst+1,cur-1){
			L[i]=max(L[i],lst+1);
			R[i]=min(R[i],cur-1);
		}
		lst=cur;
	};
	rep(i,1,m){
		if(L[i]==R[i]){
			push(i);
		}
	}
	push(m+1);
	rep(i,1,m)id[i]=i;
	sort(id+1,id+m+1,[&](int lhs,int rhs){
		if(R[lhs]-L[lhs]!=R[rhs]-L[rhs])return R[lhs]-L[lhs]<R[rhs]-L[rhs];
		if(L[lhs]!=L[rhs])return L[lhs]<L[rhs];
		if(a[lhs]!=a[rhs]) return a[lhs]<a[rhs];
		return lhs<rhs;
		
	});
	set<int>S;
	S.insert(0);
	S.insert(m+1);
	int ans=1;
	for(int l=1,r;l<=m;l=r){
		r=l+1;
		while(r<=m&&R[id[r]]-L[id[r]]==R[id[l]]-L[id[l]]&&L[id[r]]==L[id[l]]&&a[id[l]]==a[id[r]]){
			++r;
		}
		rep(_,l,r-1){
			int i=id[_];
			R[i]=min(R[i],*S.lower_bound(i)-1);
			L[i]=max(L[i],(*--S.upper_bound(i))+1);
			int tt=R[i]-L[i]+1-(query(R[i])-query(L[i]-1));
			add(L[i],1);
			ans=mu(ans,tt);
			if(tt==1){
				S.insert(L[i]);
				S.insert(R[i]);
			}
		}
	}
	for(int l=1,r;l<=m;l=r){
		r=l+1;
		while(r<=m&&R[id[r]]-L[id[r]]==R[id[l]]-L[id[l]]&&L[id[r]]==L[id[l]]&&a[id[l]]==a[id[r]]){
			++r;
		}
		ans=mu(ans,ifac[r-l]);
	}
	printf("%d\n",ans);
	return 0;
}

提出情報

ジャッジ結果