Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
41448 LYLAKIOI 【BJ】T3 C++ 运行超时 75 1000 MS 1528 KB 2125 2026-04-24 14:44:42

Tests(15/20):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int p=998244353; int n,b,a[505],f[505][515],t[515],val[515]; vector<int>E[505]; inline int qp(int a,int b){ int res=1; for(;b;b>>=1,a=a*1llu*a%p)if(b&1)res=res*1llu*a%p; return res; } int s1[1055],s2[1055],s[1055]; int iv[1055]; void dfs(int u){ f[u][0]=1; for(int x:E[u]){ dfs(x);up(i,0,b)t[i]=0; up(i,0,b)up(j,0,b-i) t[i+j]=(t[i+j]+f[u][i]*1llu*f[x][j])%p; up(i,0,b)f[u][i]=t[i]; } up(i,1,b)f[u][i]=(f[u][i]+f[u][i-1])%p; auto qu=[&](int l,int r,int x){ l-=a[u]-b,r-=a[u]-b,x-=a[u]-b;l++,r++,x++; if(s[r]==s[l-1]||s[x]!=s[x-1])return s1[r]*1llu*s2[l-1]%p*1llu*iv[x]%p; return 0llu; }; auto lag=[&](int x){ int res=0; up(i,0,b){ int P1=f[u][i]*1llu*qu(x-b,x,x-i)%p; // up(j,0,b)if(i!=j)P1=P1*1llu*(x-j+p)%p; res=(res+P1*1llu*val[i])%p; } return res; }; s1[0]=s2[0]=1,s[0]=0;up(i,1,2*b+1){ s1[i]=s1[i-1],s[i]=s[i-1]; int w=(a[u]-b+i-1+p)%p; if(w)s1[i]=s1[i]*1llu*w%p,iv[i]=qp(w,p-2); else s[i]++,iv[i]=1; s2[i]=qp(s1[i],p-2); } up(i,0,b)t[i]=lag(i+a[u]); up(i,0,b)f[u][i]=t[i]; } void slv(){ n=read(),b=n+5; up(i,2,n)E[read()].eb(i); up(i,1,n)a[i]=read(); up(i,0,b){ val[i]=1; up(j,0,b)if(i!=j)val[i]=val[i]*1llu*(i+p-j)%p; val[i]=qp(val[i],p-2); } dfs(1);printf("%d\n",f[1][0]); } int main(){ // freopen("counting.in","r",stdin),freopen("counting.out","w",stdout); slv(); return 0; }


测评信息: