QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#277905 | #5139. DFS Order 2 | zzuqy | WA | 0ms | 9808kb | C++11 | 3.5kb | 2023-12-07 08:51:52 | 2023-12-07 08:51:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char buf[1<<15],*fs,*ft;
inline char getc(){
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:* fs++;
}
inline int read(){
int This=0,F=1; char ch=getc();
while(ch<'0'||ch>'9'){
if(ch=='-') F=-1;
ch=getc();
}
while(ch>='0'&&ch<='9'){
This=(This<<1)+(This<<3)+ch-'0';
ch=getc();
}
return This*F;
}
inline void write(int x)
{
if(x==0)
{
putchar('0');
return;
}
if(x<0)
{
putchar('-');
x=-x;
}
int num=0;char ch[16];
while(x) ch[++num]=x%10+'0',x/=10;
while(num) putchar(ch[num--]);
putchar(' ');
}
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];
vector<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_back(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]--;
for(auto k:use[x])
{
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_back(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++)
write((1ll*ans[i][j]*f[i]%mod+mod)%mod);
putchar('\n');
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9808kb
input:
5 1 2 1 3 3 4 3 5
output:
4 0000 02 002 02 2 00 001 2 1 001 2 1
result:
wrong output format Expected integer, but "0000" found