QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243867#7677. Easy Diameter Problemzhoukangyang#WA 0ms18888kbC++114.3kb2023-11-08 18:43:452023-11-08 18:43:46

Judging History

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

  • [2023-11-08 18:43:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18888kb
  • [2023-11-08 18:43:45]
  • 提交

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);
}

vi 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], upl[N][N][2], upr[N][N][2];
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].emplace_back(x);
		}
	}
	
	L(d, 1, mx / 2) {
		L(e, 1, n - 1) {
			L(i, 0, n - 1) {
				
			}
		}
	}
	L(e, 1, n - 1) {
		L(d, 0, n / 2) {
			L(i, 0, sz(SZ[d][e][0])) {
				dp[d][e][i] = cur;
				cur += sz(SZ[d][e][1]) + 1;
			}
			L(o, 0, 1) {
				upl[d][e][o] = sz(SZ[d - 1][e][o]);
				upr[d][e][o] = disc[P[e][o]][d] - sz(SZ[d - 1][e][o]);
				L(i, 0, upl[d][e][o]) {
					hs[d][e][o][i] = cur;
					cur += upr[d][e][o] + 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(SZ[d - 1][e][0])) {
				L(j, 0, sz(SZ[d - 1][e][1])) if(dp[d - 1][e][i][j]) {
					if(i == sz(SZ[d - 1][e][0]) && upr[d][e][0] >= 1) {
						(hs[d][e][0][j][1] += dp[d - 1][e][i][j]) %= mod;
					} 
					
					if(j == sz(SZ[d - 1][e][1]) && upr[d][e][1] >= 1) {
						(hs[d][e][1][i][1] += dp[d - 1][e][i][j]) %= mod;
					} 
				}
			}
		}
		
		L(e, 1, n - 1) {
			L(o, 0, 1) {
				upl[d][e][o] = sz(SZ[d - 1][e][o]);
				upr[d][e][o] = disc[P[e][o]][d] - sz(SZ[d - 1][e][o]);
				L(i, 0, upl[d][e][o]) {
					L(j, 0, upr[d][e][o]) {
						if(i < upl[d][e][o]) 
							(hs[d][e][o][i + 1][j] += 
								(ll) hs[d][e][o][i][j] * (upl[d][e][o] - i) % mod) %= mod;
						if(j < upr[d][e][o]) 
							(hs[d][e][o][i][j + 1] += hs[d][e][o][i][j]) %= mod;
					}
				}
			}
		}
		
		
		L(e, 1, n - 1) {
			L(o, 0, 1) {
				L(i, 0, upl[d][e][o]) {
					L(j, 0, upr[d][e][o]) if(hs[d][e][o][i][j]) {
						int vl = hs[d][e][o][i][j];
						for(auto&t : ::e[P[e][o]]) {
							if(t == P[e][o ^ 1]) {
								if(i == upl[d][e][o]) {
									if(o == 0)
										(dp[d][e][j][1] += (ll) vl * fac[j] % mod) %= mod;
									else 
										(dp[d][e][1][j] += (ll) vl * fac[j] % mod) %= mod;
								}
							} else {
								
							}
						}
					}
				}
			}
		}
		
		L(e, 1, n - 1) {
			int u = su[e];
			int v = sv[e];
			for(auto&t : ::e[u]) if(t != v) {
				int go = ei[u][t];
			}
		}
	}
	
	if(mx & 1) {
		int ans = 0;
		L(i, 1, n - 1) 
			(ans += dp[mx / 2][i][sz(SZ[i][mx / 2][0])][sz(SZ[i][mx / 2][1])]) %= mod;
		cout << ans << '\n';
	} else {
		int gen = mx / 2;
		int ans = 0;
		L(i, 1, n - 1) 
			L(o, 0, 1)
				(ans += hs[gen][i][o][upl[gen][i][o]][upr[gen][i][o]]) %= mod;
		cout << ans << '\n';
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18888kb

input:

3
1 2
3 2

output:

0

result:

wrong answer 1st numbers differ - expected: '4', found: '0'