QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318895 | #5139. DFS Order 2 | trsins | WA | 1ms | 6084kb | C++14 | 2.1kb | 2024-02-01 09:37:52 | 2024-02-01 09:37:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=520;
const int mod=998244353;
int n,tot,head[N],fac[N],ifac[N],sz[N],ways[N],f[N][N],g[N],ans[N][N],son[N];
struct edge{int to,nxt;}e[N<<1];
void addedge(int u,int v){
e[++tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
void init(int n){
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
return;
}
void dfs(int u,int fa){
sz[u]=1,ways[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u),son[u]++;
sz[u]+=sz[v],ways[u]=ways[u]*ways[v]%mod;
}ways[u]=ways[u]*fac[son[u]]%mod;
return;
}
void dp(int u,int fa){
for(int i=0;i<=son[u];i++)for(int j=0;j<=sz[u];j++)f[i][j]=0;
f[0][0]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
for(int i=son[u];i;i--)for(int j=sz[v];j<=sz[u];j++)
f[i][j]=(f[i][j]+f[i-1][j-sz[v]])%mod;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
for(int i=1;i<=son[u];i++)for(int j=sz[v];j<=sz[u];j++)
f[i][j]=(f[i][j]-f[i-1][j-sz[v]]+mod)%mod;
for(int i=0;i<=sz[u];i++)g[i]=0;
int coef=ways[u]*qpow(ways[v],mod-2)%mod*ifac[son[u]]%mod;
for(int i=0;i<son[u];i++)for(int j=0;j<sz[u];j++)
g[j+1]=(g[j+1]+f[i][j]*fac[i]%mod*fac[son[u]-i-1]%mod*coef%mod)%mod;
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)ans[v][j]=(ans[v][j]+ans[u][i]*g[j-i]%mod)%mod;
for(int i=son[u];i;i--)for(int j=sz[v];j<=sz[u];j++)
f[i][j]=(f[i][j]+f[i-1][j-sz[v]])%mod;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dp(v,u);
}
return;
}
signed main(){
scanf("%lld",&n),init(n);
for(int i=1;i<n;i++){
int u,v;
scanf("%lld%lld",&u,&v);
addedge(u,v),addedge(v,u);
}
dfs(1,0),ans[1][1]=1,dp(1,0);
for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)printf("%lld ",ans[i][j]*ways[i]%mod);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6024kb
input:
5 1 2 1 3 3 4 3 5
output:
4 0 0 0 0 0 2 0 0 2 0 2 2 0 0 0 0 1 2 1 0 0 1 2 1
result:
ok 25 numbers
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 6084kb
input:
10 9 2 9 6 10 5 1 5 1 6 9 3 5 8 4 3 7 9
output:
24 0 0 0 0 0 0 0 0 0 0 0 0 4 2 2 8 2 2 40 0 0 0 4 4 4 4 4 4 36 0 0 0 0 4 4 8 16 16 16 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 4 2 2 8 2 2 40 0 0 6 6 0 12 0 0 42 6 0 0 12 0 0 12 0 0 72 0 0 0 6 6 0 12 0 0 42 6
result:
wrong answer 20th numbers differ - expected: '4', found: '40'