QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367182 | #5139. DFS Order 2 | Baiyu0123 | WA | 3ms | 6728kb | C++14 | 2.2kb | 2024-03-25 20:02:05 | 2024-03-25 20:02:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=505,mod=998244353;
vector<int> ed[maxn];
int d[maxn],siz[maxn],n;
int sum[maxn*2],g[maxn][maxn][maxn];
int f[maxn][maxn];
int fac[maxn],inv[maxn];
void lj(int x,int y) {
ed[x].push_back(y);
ed[y].push_back(x);
}
void init_dfs(int fa,int u) {
d[u]=ed[u].size();siz[u]=1;
for (int i=0;i<ed[u].size();i++) {
if (ed[u][i]==fa) {
for (int j=i+1;j<ed[u].size();j++) {
ed[u][j-1]=ed[u][j];
}
d[u]--;
break;
}
}
for (int i=1;i<=d[u];i++) {
int v=ed[u][i-1];
init_dfs(u,v);
siz[u]+=siz[v];
}
}
void add(int &x,int y) {
x=(x+y)%mod;
}
void output(int f[][maxn]) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
cout<<f[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void getans(int u,int l,int r,int w) {
for (int i=l;i<=r;i++) {
int v=ed[u][i-1];
for (int p=sum[w];p>=0;p--) {
for (int j=d[u]-1;j>=0;j--) {
add(g[w][p+siz[v]][j+1],g[w][p][j]);
}
}
sum[w]+=siz[v];
}
}
int tot=0;
void calc(int u,int l,int r,int w) {
if (l==r) {
int v=ed[u][l-1];
for (int k=1;k<=n-siz[u]+1;k++) {
for (int p=1;p<=siz[u]-1;p++) {
for (int j=0;j<=d[u]-1;j++) {
add(f[v][k+p],
1ll*f[u][k]*g[w][p-1][j]%mod*fac[j]%mod*fac[d[u]-j-1]%mod*inv[d[u]]%mod);
}
}
}
return ;
}
int mid=(l+r)>>1;
memcpy(g[++tot],g[w],sizeof(g[w]));sum[tot]=sum[w];
getans(u,mid+1,r,w);
getans(u,l,mid,tot);
calc(u,l,mid,w);
calc(u,mid+1,r,tot);
}
void dfs(int fa,int u) {
if (d[u]==0) return;
g[1][0][0]=1;tot=1;
calc(u,1,d[u],1);
for (int i=1;i<=tot;i++) memset(g[i],0,sizeof(g[i]));
for (int i=1;i<=d[u];i++) {
int v=ed[u][i-1];
dfs(u,v);
}
}
int qpow(int x,int y) {
ll ret=1,bas=x;
while (y) {
if (y&1) ret=ret*bas%mod;
bas=bas*bas%mod;
y>>=1;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
fac[0]=1;
for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
for (int i=0;i<=n;i++) inv[i]=qpow(fac[i],mod-2);
for (int l=2;l<=n;l++) {
int x,y;cin>>x>>y;
lj(x,y);
}
init_dfs(1,1);
f[1][1]=1;
for (int i=1;i<=n;i++) f[1][1]=1ll*f[1][1]*fac[d[i]]%mod;
dfs(1,1);
output(f);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5656kb
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: 3ms
memory: 6728kb
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 4 4 4 4 0 0 0 0 0 4 4 4 4 4 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 4 4 4 4 4 0 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 65th numbers differ - expected: '2', found: '4'