QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662799 | #5139. DFS Order 2 | Yurily | WA | 3ms | 22272kb | C++20 | 2.6kb | 2024-10-21 10:37:06 | 2024-10-21 10:37:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=505;
const long long MOD=998244353;
long long f[MAX][MAX],g[MAX],pred[MAX][MAX][MAX],d[MAX][MAX],A[MAX];
struct edge{
int nxt,to;
};
int h[MAX],tot,son[MAX];
edge e[MAX*2];
int n,tmp[MAX];
void pre(int u,int fa){
son[u]=1;
g[u]=1;
int cnt=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)
continue;
pre(v,u);
cnt++;
son[u]+=son[v];
g[u]=g[u]*g[v]%MOD;
}
g[u]=g[u]*A[cnt]%MOD;
}
long long quick_pow(long long x,long long y){
long long res=1;
while(y){
if(y&1)
res=res*x%MOD;
x=x*x%MOD;
y>>=1;
}
return res;
}
void pre_dp(int u,int fa){
int cnt=0;
long long s=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)
continue;
tmp[++cnt]=v;
s=s*g[v]%MOD;
}
for(int i=1;i<=cnt;++i){
pred[tmp[i]][0][0]=1;
for(int j=1;j<=cnt;++j){
if(j==i)
continue;
for(int k=1;k<=son[u]-son[tmp[i]]-1;++k){
for(int l=j-(j>=i?1:0);l>=1;--l){
if(k-son[tmp[j]]>=0)
pred[tmp[i]][k][l]=(pred[tmp[i]][k][l]+pred[tmp[i]][k-son[tmp[j]]][l-1])%MOD;
}
}
}
for(int k=0;k<=son[u]-son[tmp[i]]-1;++k){
for(int l=0;l<=cnt-1;++l){
// cout<<tmp[i]<<" "<<k<<" "<<l<<" "<<pred[tmp[i]][k][l]<<endl;
d[tmp[i]][k]=(d[tmp[i]][k]+(__int128)pred[tmp[i]][k][l]*A[l]*A[cnt-1-l]*s*quick_pow(g[tmp[i]],MOD-2)%MOD)%MOD;
}
}
}
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)
continue;
pre_dp(v,u);
}
}
void dp(int u,int k,int fa){
int cnt=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)
continue;
tmp[++cnt]=v;
}
for(int i=1;i<=cnt;++i){
for(int j=1;j<=son[u]-son[tmp[i]];++j){
if(k-j>=0)
f[tmp[i]][k]=(f[tmp[i]][k]+f[u][k-j]*d[tmp[i]][j-1]%MOD)%MOD;
}
// cout<<"*"<<tmp[i]<<" "<<k<<" "<<f[tmp[i]][k]<<endl;
}
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)
continue;
dp(v,k,u);
}
}
// ¿ì¶Á
int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-'){
f = -1;
}
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
void addedge(int u,int v){
e[++tot].to=v;
e[tot].nxt=h[u];
h[u]=tot;
}
int main(){
cin>>n;
A[0]=1;
for(int i=1;i<=n;++i)
A[i]=A[i-1]*i%MOD;
for(int i=1;i<=n-1;++i){
int u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
pre(1,0);
d[1][0]=1;
pre_dp(1,0);
f[0][0]=1;
f[1][1]=1;
for(int i=1;i<=n;++i)
dp(1,i,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");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13972kb
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: 0ms
memory: 22272kb
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 8 4 4 8 0 0 0 0 0 4 4 8 4 4 8 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 6 8 2 6 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 26th numbers differ - expected: '4', found: '8'