QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244213#7677. Easy Diameter ProblemzhoukangyangWA 3ms70644kbC++115.4kb2023-11-08 21:59:002023-11-08 21:59:01

Judging History

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

  • [2023-11-08 21:59:01]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:70644kb
  • [2023-11-08 21:59:00]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define i128 __int128
using namespace std;
const int N = 307, S = 5e7, mod = 998244353;
int n;
int qpow(int x, int y = mod - 2) {
	int res = 1;
	for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
	return res;
}
int fac[N], ifac[N], inv[N];
void init(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	L(i, 2, x) inv[i] = (ll) (mod - mod / i) * inv[mod % i] % mod;
	L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
} 
int C(int x, int y) {
	return x < y || y < 0 ? 0 : (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int sgn(int x) {
	return (x & 1) ? mod - 1 : 1;
}

vi e[N];
int rt;
int su[N], sv[N], P[N][2];
int dist[N][N];
void dfs(int x, int fa) {
	for(auto&v : e[x]) if(v != fa) 
		dist[rt][v] = dist[rt][x] + 1, dfs(v, x);
}

int SZ[N][N][2];
int *dp[N][N][N], pool[S], *cur = pool;
int ei[N][N];

int disc[N][N];
int *hs[N][N][2][N];
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	init(n + 1);
	if(n == 1) {
		cout << 1 << '\n';
		return 0;
	}
	L(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		P[i][0] = u, P[i][1] = v;
		ei[u][v] = ei[v][u] = i;
		su[i] = u, sv[i] = v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	} 
	L(i, 1, n) {
		L(j, 1, n) {
			disc[i][dist[i][j]] += 1;
		}
	}
	for(rt = 1; rt <= n; ++rt) 
		dfs(rt, 0);
	
	int mx = 0;
	L(i, 1, n) 
		L(j, 1, n) 
			mx = max(mx, dist[i][j]);
	L(i, 1, n - 1) {
		L(d, 0, mx / 2) {
			L(o, 0, 1)
				L(x, 1, n) 
					if(dist[P[i][o]][x] == d && dist[P[i][o ^ 1]][x] == d + 1) 
						SZ[d][i][o] += 1;
		}
	}
	L(e, 1, n - 1) {
		L(d, 0, n / 2) {
			L(i, 0, SZ[d][e][0]) 
				dp[d][e][i] = cur, cur += SZ[d][e][1] + 1;
			L(o, 0, 1) if(d) {
				L(i, 0, SZ[d - 1][e][o]) {
					hs[d][e][o][i] = cur, cur += SZ[d][e][o ^ 1] + 1;
				}
			}
		}
	}
	L(i, 1, n - 1) 
		dp[0][i][1][1] = 2;
	L(d, 1, mx / 2) {
		L(e, 1, n - 1) {
			int u = su[e];
			int v = sv[e];
			
			L(i, 0, SZ[d - 1][e][0])
				L(j, 0, SZ[d - 1][e][1]) if(dp[d - 1][e][i][j]) {
					int vl = dp[d - 1][e][i][j];
					if(i == SZ[d - 1][e][0]) {
						for(auto&t : ::e[u]) {
							int E = ei[u][t];
							int op = P[E][1] == t;
							if(t != v && SZ[d - 1][E][op] > 0) {
								(hs[d][E][op][1][j] += (ll) vl * SZ[d - 1][E][op] % mod) %= mod;
								int hr = SZ[d][e][0] - SZ[d - 1][E][op];
								if(hr) (hs[d][E][op][0][j + 1] += (ll) vl * hr % mod) %= mod;
							}
							if(t == v && SZ[d - 1][E][op] > 0) {
								(hs[d][E][op][j][1] += (ll) vl * SZ[d][E][op ^ 1] % mod) %= mod;
							}
						}
					}
					if(j == SZ[d - 1][e][1]) {
						for(auto&t : ::e[v]) {
							int E = ei[v][t];
							int op = P[E][1] == t;
							if(t != u && SZ[d - 1][E][op] > 0) {
								(hs[d][E][op][1][i] += (ll) vl * SZ[d - 1][E][op] % mod) %= mod;
								int hr = SZ[d][e][1] - SZ[d - 1][E][op];
								if(hr) (hs[d][E][op][0][i + 1] += (ll) vl * hr % mod) %= mod;
							}
							if(t == u && SZ[d - 1][E][op] > 0) {
								(hs[d][E][op][i][1] += (ll) vl * SZ[d][E][op ^ 1] % mod) %= mod;
							}
						}
					}
				}
		}
		L(e, 1, n - 1) L(o, 0, 1) {
			int lv = SZ[d - 1][e][o], rv = SZ[d][e][o ^ 1];
			L(i, 0, lv) {
				L(j, 0, rv) if(hs[d][e][o][i][j]) {
					if(i < lv) 
						(hs[d][e][o][i + 1][j] += (ll)hs[d][e][o][i][j] * (lv - i) % mod) %= mod;
					if(j < rv) 
						(hs[d][e][o][i][j + 1] += (ll)hs[d][e][o][i][j] * (rv - j) % mod) %= mod;
				}
			}
		}
		L(e, 1, n - 1) L(o, 0, 1) if(SZ[d][e][o]) {
			int lv = SZ[d - 1][e][o], rv = SZ[d][e][o ^ 1];
			L(j, 0, rv) if(hs[d][e][o][lv][j]) {
				int mv = (ll) hs[d][e][o][lv][j] * SZ[d][e][o] % mod;
				if(!o) {
					(dp[d][e][1][j] += mv) %= mod;
				} else {
					(dp[d][e][j][1] += mv) %= mod;
				}
			}
		}
		
		L(e, 1, n - 1) {
			int lv = SZ[d][e][0], rv = SZ[d][e][1];
			L(i, 0, lv) {
				L(j, 0, rv) if(dp[d][e][i][j]) {
					if(i < lv) 
						(dp[d][e][i + 1][j] += (ll)dp[d][e][i][j] * (lv - i) % mod) %= mod;
					if(j < rv) 
						(dp[d][e][i][j + 1] += (ll)dp[d][e][i][j] * (rv - j) % mod) %= mod;
				}
			}
		}
//		L(e, 1, n - 1) {
//			int lv = SZ[d][e][0], rv = SZ[d][e][1];
//			L(i, 0, lv) {
//				L(j, 0, rv) if(dp[d][e][i][j]) {
//					cout << P[e][0] << ' ' << P[e][1] << ", " << d << " with " 
//						<< i << ' ' << j << " : " << dp[d][e][i][j] << endl;
//				}
//			}
//		}
	}
	
	if(mx & 1) {
		int gen = mx / 2;
		int ans = 0;
		L(i, 1, n - 1) 
			(ans += dp[gen][i][SZ[gen][i][0]][SZ[gen][i][1]]) %= mod;
		cout << ans << '\n';
	} else {
		int gen = (mx - 1) / 2;
		int ans = 0;
		L(e, 1, n - 1) {
			int lv = SZ[gen][e][0];
			int rv = SZ[gen][e][1];
			L(i, 0, lv) {
				L(j, 0, rv) if(dp[gen][e][i][j]) {
					int vl = dp[gen][e][i][j];
					if(SZ[gen + 1][e][0] && i == lv) {
						(ans += (ll) fac[SZ[gen + 1][e][0] + rv - j - 1] * vl % mod) %= mod;
					} 
					if(SZ[gen + 1][e][1] && j == lv) {
						(ans += (ll) fac[SZ[gen + 1][e][1] + lv - i - 1] * vl % mod) %= mod;
					} 
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11860kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11860kb

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 2ms
memory: 13936kb

input:

7
5 7
2 5
2 1
1 6
3 6
4 1

output:

116

result:

ok 1 number(s): "116"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 70644kb

input:

100
89 60
66 37
59 74
63 49
69 37
9 44
94 22
70 30
79 14
25 33
23 4
78 43
63 30
95 7
6 59
56 31
21 56
58 43
95 28
81 19
63 40
58 87
81 38
100 55
78 23
37 78
86 70
33 11
52 17
42 19
19 13
70 100
97 79
66 67
66 27
82 55
15 27
68 33
97 26
46 20
70 93
1 10
69 79
81 45
58 95
24 63
79 51
85 11
12 43
41 64...

output:

676340329

result:

wrong answer 1st numbers differ - expected: '748786623', found: '676340329'