QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#621434#5139. DFS Order 2yzj123WA 0ms3668kbC++202.8kb2024-10-08 14:30:082024-10-08 14:30:29

Judging History

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

  • [2024-10-08 14:30:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3668kb
  • [2024-10-08 14:30:08]
  • 提交

answer

#include<bits/stdc++.h>
using i64 = long long;
#define int i64
const int mod = 998244353;
void solve() {
	int n;
	std::cin >> n;
	std::vector<int> fac(n + 1);
	fac[0] = 1;
	for (int i = 1; i <= n; i ++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	std::vector<std::vector<int> > e(n + 1);
	e[1].push_back(0);
	for (int i = 1; i < n; i ++) {
		int u, v;
		std::cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	std::vector<int> siz(n + 1), inner(n + 1, 1);
	auto dfs1 = [&](auto self, int u, int p) -> void {
		siz[u] = 1;
		for (auto v : e[u]) {
			if (v == p) continue;
			self(self, v, u);
			siz[u] += siz[v];
			inner[u] = inner[u] * inner[v] % mod;
		}
		inner[u] = inner[u] * fac[e[u].size() - 1] % mod;
	};
	dfs1(dfs1, 1, 0);
	std::vector<std::vector<int> > ans(n + 1, std::vector<int>(n + 1));
	std::vector<std::vector<int> > dp(n + 2, std::vector<int>(n + 2));
	dp[0][1] = 1;
	auto dfs = [&](auto self, int u, int p) -> void {
		auto roback = dp;
		for (int i = 0; i <= n; i ++) {
			for (int j = n; j >= 1; j --) {
				dp[i][j] = dp[i][j - 1];
			}
		}
		int o = 1;
		std::vector<int> son;
		for (auto v : e[u]) {
			if (v == p) continue;
			o = o * inner[v] % mod;
		}
		for (auto v : e[u]) {
			if (v == p) continue;
			for (int i = n; i >= 1; i --) {
				for (int j = n; j >= siz[v]; j --) {
					if (dp[i - 1][j - siz[v]]) {
						dp[i][j] += dp[i - 1][j - siz[v]] * i % mod;
						dp[i][j] %= mod;
					}
				}
			}
		}
		int opp = (int)e[u].size() - 2;
		if (opp < 0) opp = 0;
		o = o * fac[opp] % mod;

		for (auto v : e[u]) {
			if (v == p) continue;
			for (int i = 1; i <= n; i ++) {
				for (int j = n; j >= siz[v]; j --) {
					if (dp[i - 1][j - siz[v]]) {
						dp[i][j] -= dp[i - 1][j - siz[v]] * i % mod;
						dp[i][j] = (dp[i][j] % mod + mod) % mod;
					}
				}
			}
			for (int i = 0; i <= n; i ++) {
				for (int j = 0; j <= n; j ++) {
					if (dp[j][i]) {
						ans[v][i] = (ans[v][i] + dp[j][i] * o % mod) % mod;
					}
				}
			}
			auto op = dp;
			for (int i = 1; i <= n; i ++) {
				for (int j = 0; j <= n; j ++) {
					dp[0][j] = (dp[0][j] + dp[i][j]) % mod;
					dp[i][j] = 0;
				}
			}
			self(self, v, u);
			dp = op;
			for (int i = n; i >= 1; i --) {
				for (int j = n; j >= siz[v]; j --) {
					if (dp[i - 1][j - siz[v]]) {
						dp[i][j] += dp[i - 1][j - siz[v]] * i % mod;
						dp[i][j] %= mod;
					}
				}
			}
		}
		dp = roback;
	};
	dfs(dfs, 1, 0);
	ans[1][1] = inner[1];
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			std::cout << (ans[i][j] + mod) % mod << ' ';
		}
		std::cout << '\n';
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1;
	// std::cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}

详细

Test #1:

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

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

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 2 2 2 6 2 2 4 
0 0 0 2 4 4 2 4 4 0 
0 0 0 0 1 2 2 1 2 2 
0 12 0 0 0 0 0 12 0 0 
0 12 0 0 12 0 0 0 0 0 
0 0 0 2 2 2 6 2 2 4 
0 0 1 1 0 0 0 0 1 1 
0 0 6 0 0 6 0 0 0 0 
0 0 1 1 0 0 0 0 1 1 

result:

wrong answer 14th numbers differ - expected: '4', found: '2'