QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367182#5139. DFS Order 2Baiyu0123WA 3ms6728kbC++142.2kb2024-03-25 20:02:052024-03-25 20:02:06

Judging History

你现在查看的是最新测评结果

  • [2024-03-25 20:02:06]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6728kb
  • [2024-03-25 20:02:05]
  • 提交

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'