QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373391 | #5139. DFS Order 2 | Siilhouette | WA | 1ms | 5792kb | C++14 | 3.8kb | 2024-04-01 15:59:57 | 2024-04-01 15:59:59 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
#define fir first
#define sec second
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int N=510;
int n,m,soncnt[N];
ll fac[N],g[N],ans[N][N],h[N][N],siz[N],f[N];
inline ll fpow(ll x,ll y)
{
ll res=1;
for(;y;y>>=1)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
}
return res;
}
struct Graph{
int tot,head[N],suiv[N<<1],ver[N<<1],fa[N];
inline void lnk(int x,int y)
{
ver[++tot]=y;
suiv[tot]=head[x];
head[x]=tot;
}
inline void dfs1(int x)
{
g[x]=1;siz[x]=1;
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i];
if(y==fa[x])continue;
fa[y]=x;
dfs1(y);
siz[x]+=siz[y];
soncnt[x]++;
g[x]=g[x]*g[y]%mod;
}
g[x]=g[x]*fac[soncnt[x]]%mod;
}
inline void dfs2(int x)
{
//cout<<" x "<<x<<endl;
h[0][0]=1;
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i];
if(y==fa[x])continue;
for(int k=soncnt[x];k;k--)
for(int l=siz[x];l-siz[y]>=0;l--)
h[k][l]=(h[k][l]+h[k-1][l-siz[y]])%mod;
}
/*
for(int k=soncnt[x];k>=0;k--)
{
cout<<"h[][] "<<endl;
for(int l=siz[x];l>=0;l--)
cout<<"k L "<<k<<" "<<l<<" "<<h[k][l]<<endl;
}
*/
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i];
if(y==fa[x])continue;
for(int k=1;k<=soncnt[x];k++)
for(int l=siz[x];l-siz[y]>=0;l--)
h[k][l]=((h[k][l]-h[k-1][l-siz[y]])%mod+mod)%mod;
for(int k=0;k<=siz[x]+1;k++)
f[k]=0;
for(int k=0;k<=soncnt[x]-1;k++)
for(int l=0;l<=siz[x];l++)
f[l+1]=(f[l+1]+fac[k]*fac[soncnt[x]-1-k]%mod*h[k][l]%mod)%mod;
for(int k=1;k<=n;k++)
for(int l=1;l+k<=n;l++)
ans[y][l+k]=(ans[y][l+k]+ans[x][k]*f[l]%mod)%mod;
for(int k=soncnt[x];k;k--)
for(int l=siz[x];l-siz[y]>=0;l--)
h[k][l]=(h[k][l]+h[k-1][l-siz[y]])%mod;
/*
for(int k=0;k<=soncnt[z]-1;k++)
for(int j=0;j<=n;j++)
for(int l=n;l-j>=0;l--)
f[z][l]=(f[z][l]+f[fa[z]][l-j]*h[k][j]%mod*fac[k]%mod*fac[soncnt[z]-k-1]%mod)%mod;
cout<<"f[][]"<<endl;
for(int j=0;j<=siz[x];j++)
cout<<"z j "<<z<<" "<<f[j]<<endl;*/
}
for(int i=0;i<=soncnt[x];i++)
for(int j=0;j<=siz[x];j++)
h[i][j]=0;
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i];
if(y==fa[x])continue;
dfs2(y);
}
}
}e;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fac[0]=1;
for(int i=1;i<=500;i++)
fac[i]=fac[i-1]*i%mod;
cin>>n;
for(int i=1,x,y;i<n;i++)
cin>>x>>y,e.lnk(x,y),e.lnk(y,x);
e.dfs1(1);
ans[1][1]=g[1];
e.dfs2(1);
for(int i=1;i<=n;i++)
{
ll sum=0;
for(int j=1;j<=n;j++)
sum=(sum+ans[i][j])%mod;
ll inv=fpow(sum,mod-2);
for(int j=1;j<=n;j++)
cout<<(g[1]*ans[i][j]%mod*inv%mod)<<" ";
cout<<endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5656kb
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: 5792kb
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 4 0 0 0 4 4 4 4 4 4 0 0 0 0 0 2 2 2 6 6 6 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 4 0 0 6 6 0 0 0 0 6 6 0 0 12 0 0 12 0 0 0 0 0 0 6 6 0 0 0 0 6 6
result:
wrong answer 35th numbers differ - expected: '4', found: '2'