QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#617937#5139. DFS Order 2MENDAXWA 0ms3872kbC++142.0kb2024-10-06 17:47:412024-10-06 17:47:41

Judging History

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

  • [2024-10-06 17:47:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3872kb
  • [2024-10-06 17:47:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define x first
#define y second
const int N=510,mod=998244353;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef pair<int,int> PII;

vector<int> e[N];

int qmi(int a,int k){
	int res=1;
	while(k){
		if(k&1) res=res*a%mod;
		a=a*a%mod;
		k>>=1;
	}
	return res;
}

int p[N][N],siz[N];

int ge(int u,int fa){
	int num=0;
	int res=1;
	siz[u]=1;
	for(auto v:e[u]){
		if(v==fa) continue;
		num++;
		res*=ge(v,u);
		siz[u]+=siz[v];
		res%=mod;
	}
	for(int i=1;i<=num;i++)res*=i,res%=mod;
	return res;
}

int pos[N];
int n;

void dfs(int u,int fa){
	vector<int> w;
	w.push_back(0);
	int cnt=0;
	for(auto v:e[u]){
		if(v==fa) continue;
		cnt++;
		pos[v]=cnt;
		w.push_back(siz[v]);
	}
	int len=w.size();
	
	for(auto v:e[u]){//这个就是枚举要处理的子儿子 
		vector<vector<int>> dp(len+1,vector<int>(siz[u]+10,0));
		dp[0][1]=1;
		if(v==fa) continue;
		for(int i=1;i<len;i++){
			for(int j=0;j<=siz[u];j++) dp[i][j]=dp[i-1][j];
			if(i==pos[v]) continue;//求得v
			for(int j=0;j<=siz[u];j++)if(j>=w[i]) dp[i][j]+=dp[i-1][j-w[i]],dp[i][j]%=mod;//这里面dp[i][4] 
		}
		int sum=0;
		for(int j=0;j<=siz[u];j++) sum+=dp[len-1][j];
		sum=qmi(sum,mod-2);
		for(int i=1;i<=n;i++){//枚举u走的步数 
			for(int j=1;j<=n;j++){//枚举兄弟走的步数 
				p[v][i+j]+=dp[len-1][j]%mod*sum%mod*p[u][i]%mod;//兄弟的方案数 
				p[v][i+j]%=mod;
			}
		}
	}
	for(auto v:e[u]){
		if(v==fa) continue;
		dfs(v,u);
	}
}

void slove(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
	}
	int total=ge(1,0);
//	cout<<total<<endl;
	p[1][1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<p[i][j]*total%mod<<" ";
		}
		cout<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int T=1;
	while(T--) slove();
} 

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

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: 3872kb

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 3 3 3 6 3 3 3 
0 0 0 3 6 3 3 6 3 0 
0 0 0 0 3 6 3 3 6 3 
0 12 0 0 0 0 0 12 0 0 
0 12 0 0 12 0 0 0 0 0 
0 0 0 3 3 3 6 3 3 3 
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 14th numbers differ - expected: '4', found: '3'