QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667567#5139. DFS Order 2HHAZWA 1ms5816kbC++203.7kb2024-10-23 00:16:062024-10-23 00:16:06

Judging History

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

  • [2024-10-23 00:16:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5816kb
  • [2024-10-23 00:16:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef pair<ld,ld>pdd;
typedef pair<ll, pair<ll, ll> > plpair;
typedef vector<int> vi;
typedef vector<ll> vl;
#define endl '\n'
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(id) id & (-id)
#define fi first
#define sec second
#define lc id<<1
#define rc id<<1|1
#define sz(x) (int)(x).size()
#define all(t) (t).begin(), (t).end()
#define meh {cout<<"NO"<<endl;return;}
#define yay {cout<<"YES"<<endl;return;}
#define vin(v) for(auto&x:v)cin>>x;
#define print(v) for (auto x: v)cout<<x<<' ';cout<<endl;
#define sqrt(x) sqrtl(x)
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 505;
const int mod = 998244353;

ll n;
ll dp[N][N], ans[N][N];
ll f[N], val[N], siz[N], son[N], g[N];
vector<ll>ve[N];

ll qsm(ll n,ll b, ll Mod = 998244353){
	n = n % Mod;
	ll s = 1,a = n;
	while(b){
		a = a % Mod;
		if(b&1)
			s = s * a;
		b >>= 1;
		a = a * a;
		s = s % Mod;
	}
	return s;
}

void init_dfs(ll u, ll fa) {
	siz[u]++;
	ll j = 1;
	for(auto v : ve[u]) {
		if(v != fa) {
			init_dfs(v, u);
			siz[u] += siz[v];
			son[u]++;
			j *= val[v];
			j %= mod;
		}
	}
	val[u] = j * f[son[u]] % mod;
}

void dfs(ll u, ll fa) {
	rep(i, 0, son[u]) {
		rep(j, 0, siz[u]) {
			dp[i][j] = 0;
		}
	}
	dp[0][0] = 1;
	ll d = 1;
	for(auto v : ve[u]) {
		if(v != fa) {
			d *= val[v];
			per(i, son[u], 1) {
				per(j, siz[u], siz[v]) {
					dp[i][j] += dp[i - 1][j - siz[v]];
					dp[i][j] %= mod;
				}
			}
		}
	}
	for(auto v : ve[u]) {
		if(v != fa) {
			rep(i, 0, 500) {
				g[i] = 0;
			}
			rep(i, 1, son[u]) {
				rep(j, siz[v], siz[u]) {
					dp[i][j] -= dp[i - 1][j - siz[v]];
					dp[i][j] = (dp[i][j] + mod) % mod;
					// if(v==3 && dp[i][j]) cout << i << ' ' << j << ' ' << dp[i][j] << endl;
				}
			}
			rep(i, 0, son[u] - 1) {
				rep(j, 0, siz[u]) {
					g[j] += ((((dp[i][j] * f[i]) % mod) * f[son[u] - 1 - i]) % mod) * d % mod;
					g[j] % mod;
					// if(v==3 && dp[i][j]) cout << i << ' ' << j << ' ' << ((((dp[i][j] * f[i]) % mod) * f[son[u] - 1 - i]) % mod) * d % mod << endl;
				}
			}
			// if(v==3)
			// rep(j, 0, son[u]) {
			// 	debug(g[j]);
			// }
			rep(i, 1, n) {
				rep(j, i + 1, n) {
					if(ans[u][i]) {
						ans[v][j] += g[j - i - 1];
						ans[v][j] %= mod;
					}
				}
			}
			per(i, son[u], 1) {
				per(j, siz[u], siz[v]) {
					dp[i][j] += dp[i - 1][j - siz[v]];
					dp[i][j] %= mod;
				}
			}
		}
	}
	for(auto v : ve[u]) {
		if(v != fa) {
			dfs(v, u);
		}
	}
}

void solve() {
	cin >> n;
	f[0] = 1;
	rep(i, 1, n) {
		f[i] = f[i - 1] * i % mod;
	}
	rep(i, 2, n) {
		ll u, v;
		cin >> u >> v;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	init_dfs(1, 0);
	ans[1][1] = val[1];
	dfs(1, 0);
	rep(i, 1, n) {
		rep(j, 1, n) {
			cout << ans[i][j] << " \n"[j == n];
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	// cin >> T;
	//	cout.flush();
	//		ofstream outfile("C:\\Users\\86187\\OneDrive\\桌面\\1.txt");
	//		outfile << "a[1]=0;a[2]=1;";
	//		ll l = 1e7 + 1;
	//		rep(i, 3, 1e9) {
	//			printf("%lld\n", i);
	//			ll x = (i - 1) * ((a[i - 1] + a[i - 2]) % mod);
	//			x %= mod;
	//			if(i == l) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//			}
	//			if(i == l + 1) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//				l += 1e7;
	//			}
	//		}
	while(T--) {
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5684kb

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

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