QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277900 | #5139. DFS Order 2 | zzuqy | RE | 0ms | 0kb | C++11 | 3.0kb | 2023-12-07 08:48:54 | 2023-12-07 08:48:54 |
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],F[510],JIE[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<int>q;
int vis[510][510];
queue<int>use[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;
JIE[0]=1;
for(int i=1;i<=n+1;i++){
jie[i]=1ll*jie[i-1]*i%mod;
JIE[i]=quick(jie[i],mod-2);
}
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;
}
}
ans[1][1]=1;
for(int i=1;i<=n;i++)
F[i]=quick(f[i],mod-2);
q.push(1);
use[1].push(1);
while(q.size())
{
int x=q.front();
q.pop();
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]--;
while(use[x].size())
{
int k=use[x].front();
use[x].pop();
int res=ans[x][k];
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*F[y]%mod*JIE[cnt[x]+1]%mod;
ans[y][k+i+1]%=mod;
}
}
}
q.push(y);
for(int i=0;i<=n;i++)
if(ans[y][i])
use[y].push(i);
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;
}
}
// cout<<clock();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<(1ll*ans[i][j]*f[i]%mod+mod)%mod<<' ';
cout<<'\n';
}
}
详细
Test #1:
score: 0
Runtime Error
input:
5 1 2 1 3 3 4 3 5