QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727142 | #5139. DFS Order 2 | sslwcr | WA | 2ms | 7116kb | C++14 | 2.5kb | 2024-11-09 11:40:37 | 2024-11-09 11:40:38 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#include<array>
#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int ret,c,f=1;
while (((c=getchar())> '9'||c< '0')&&c!='-');
if (c=='-') f=-1,ret=0;
else ret=c-'0';
while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*f;
}
int n,f[505][505],sz[505],fac[505],inv[505],g[505],w[505][505],V[505];
vector<int> ed[505];
int ksm(int x,int y)
{
int v=1;
while (y)
{
if (y&1) v=v*x%mod;
x=x*x%mod;
y>>=1;
}
return v;
}
void dfs(int x,int fa)
{
g[x]=1;
sz[x]=1;
int cnt=0;
for (int to:ed[x])
{
if (to==fa) continue;
dfs(to,x);
g[x]=g[x]*g[to]%mod;
sz[x]+=sz[to];
++cnt;
}
g[x]=g[x]*fac[cnt]%mod;
return;
}
void dfs2(int x,int fa)
{
memset(w,0,sizeof(w));
w[0][0]=1;
int fv=1,cnt=0;
for (int to:ed[x])
{
if (to==fa) continue;
fv=fv*g[to]%mod;
++cnt;
for (int i=cnt;i>=1;--i) for (int j=n;j>=sz[to];--j)
{
w[j][i]+=w[j-sz[to]][i-1]*i%mod;
w[j][i]>=mod?w[j][i]-=mod:0;
}
}
for (int to:ed[x])
{
if (to==fa) continue;
for (int i=1;i<=cnt;++i) for (int j=sz[to];j<=n;++j)
{
w[j][i]-=w[j-sz[to]][i-1]*i%mod;
w[j][i]<0?w[j][i]+=mod:0;
}
for (int j=0;j<=n;++j) V[j]=0;
for (int j=0;j<=n;++j) for (int i=0;i<=cnt;++i) V[j]=V[j]+w[j][i]>=mod?V[j]+w[j][i]-mod:V[j]+w[j][i];
fv=fv*ksm(g[to],mod-2)%mod;
for (int j=1;j<=n;++j) for (int k=0;k<j;++k)
{
f[to][j]+=f[x][j-k-1]*V[k]%mod*fv%mod*V[sz[x]-1-sz[to]-k]%mod;
if (f[to][j]>=mod) f[to][j]-=mod;
}
for (int i=cnt;i>=1;--i) for (int j=n;j>=sz[to];--j)
{
w[j][i]+=w[j-sz[to]][i-1]*i%mod;
w[j][i]>=mod?w[j][i]-=mod:0;
}
fv=fv*g[to]%mod;
}
for (int to:ed[x])
{
if (to==fa) continue;
dfs2(to,x);
}
return;
}
signed main()
{
n=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
ed[x].emplace_back(y);
ed[y].emplace_back(x);
}
fac[0]=1;
inv[0]=1;
for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2);
for (int i=n;i>=1;i--) inv[i-1]=inv[i]*i%mod;
f[1][1]=1;
dfs(1,0);
dfs2(1,0);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) printf("%lld ",f[i][j]*g[i]%mod);
printf("\n");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7116kb
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: 2ms
memory: 5900kb
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 8 4 4 8 4 0 0 0 0 0 4 8 4 4 8 4 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 25th numbers differ - expected: '4', found: '8'