QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#244213 | #7677. Easy Diameter Problem | zhoukangyang | WA | 3ms | 70644kb | C++11 | 5.4kb | 2023-11-08 21:59:00 | 2023-11-08 21:59:01 |
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);
}
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'