QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277741 | #5139. DFS Order 2 | zzuqy# | WA | 0ms | 9596kb | C++11 | 2.5kb | 2023-12-06 22:11:41 | 2023-12-06 22:11:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
int x;cin>>x;
return x;
}
int mod=998244353;
ll quick(ll a,ll b)
{
ll t=1;
while(b)
{
if(b&1)
t=t*a%mod;
b=b/2;
a=a*a%mod;
}
return t;
}
int n,f[510],siz[510],g[510][510][510],jie[510],ans[510][510];
int sum[510],cnt[510];
vector<int>e[510];
void dfs(int x,int fa)
{
f[x]=1;
siz[x]=1;
for(int i=0;i<e[x].size();i++)
{
if(e[x][i]==fa)
{
swap(e[x][i],e[x][e[x].size()-1]);
e[x].resize(e[x].size()-1);
}
}
for(auto y:e[x])
{
if(y==fa)
continue;
dfs(y,x);
siz[x]+=siz[y];
f[x]=1ll*f[x]*f[y]%mod;
cnt[x]++;
}
f[x]=1ll*f[x]*jie[cnt[x]]%mod;
}
queue<pair<int,int>>q;
int vis[510][510];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
e[x].push_back(y);
e[y].push_back(x);
}
jie[0]=1;
for(int i=1;i<=n+1;i++)
jie[i]=1ll*jie[i-1]*i%mod;
dfs(1,0);
for(int x=n;x>=1;x--)
{
g[x][0][0]=1;
cnt[x]=0;
for(auto y:e[x])
{
sum[x]+=siz[y];
cnt[x]++;
for(int i=sum[x];i>=siz[y];i--)
for(int j=cnt[x];j>=1;j--)
g[x][j][i]=(g[x][j][i]+g[x][j-1][i-siz[y]])%mod;
}
}
q.push({1,1});
vis[1][1]=1;
ans[1][1]=1;
while(q.size())
{
int x=q.front().first,k=q.front().second;
q.pop();
int res=ans[x][k];
for(auto y:e[x])
{
for(int i=siz[y];i<=sum[x];i++)
for(int j=1;j<=cnt[x];j++)
g[x][j][i]=(g[x][j][i]-g[x][j-1][i-siz[y]])%mod;
sum[x]-=siz[y];
cnt[x]--;
for(int i=0;i<=sum[x];i++)
{
for(int j=0;j<=cnt[x];j++)
{
if(g[x][j][i]==0)
continue;
ans[y][k+i+1]+=1ll*res*jie[j]%mod*jie[cnt[x]-j]%mod*g[x][j][i]%mod*f[x]%mod*quick(f[y],mod-2)%mod*quick(jie[cnt[x]+1],mod-2)%mod;
ans[y][k+i+1]%=mod;
}
}
sum[x]+=siz[y];
cnt[x]++;
for(int j=cnt[x];j>=1;j--)
for(int i=1;i<=sum[x];i++)
g[x][j][i]=(g[x][j][i]+g[x][j-1][i-siz[y]])%mod;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<(ans[i][j]*f[i]%mod+mod)%mod<<' ';
cout<<'\n';
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9596kb
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 0 0 0 0 0 0 0 0
result:
wrong answer 18th numbers differ - expected: '1', found: '0'