QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243867 | #7677. Easy Diameter Problem | zhoukangyang# | WA | 0ms | 18888kb | C++11 | 4.3kb | 2023-11-08 18:43:45 | 2023-11-08 18:43:46 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'