QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283686 | #7677. Easy Diameter Problem | A_programmer | WA | 19ms | 38496kb | C++14 | 3.6kb | 2023-12-15 10:04:14 | 2023-12-15 10:04:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll mod = 998244353;
int n, len, Mid;
int U[305], V[305], cnt[1205][305], dis[605][605];
ll dp[2][1205][305], fac[2005], C[2005][2005];
vector<pii> g[605];
void precalc(int x)
{
fac[0] = C[0][0] = 1;
for (int i = 1; i <= x; i++)
{
fac[i] = fac[i - 1] * i % mod;
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
ll Ch(int n, int m) { return C[n + m - 1][n - 1]; } //n个盒子,填m个数,可空
void calc(int u, int fu, int id)
{
for (pii tmp : g[u])
{
int v = tmp.first;
if (v == fu) continue;
dis[id][v] = dis[id][u] + 1;
calc(v, u, id);
}
}
void travel(int st, int u, int fu, int dep)
{
cnt[st][dep]++;
for (pii tmp : g[u])
{
int v = tmp.first;
if (v == fu) continue;
travel(st, v, u, dep + 1);
}
}
void init()
{
for (int i = 1; i <= 2 * n - 1; i++) calc(i, 0, i);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dis[i][j] > len)
{
len = dis[i][j];
for (int k = 1; k < 2 * n; k++)
if (dis[i][j] == dis[i][k] + dis[k][j] && dis[i][k] == dis[k][j])
{
Mid = k;
break;
}
}
len >>= 1;
for (int i = 1; i <= n - 1; i++)
{
travel(4 * (i - 1), V[i], i + n, 0);
travel(4 * (i - 1) + 1, U[i], i + n, 0);
travel(4 * (i - 1) + 2, i + n, U[i], 0);
travel(4 * (i - 1) + 3, i + n, V[i], 0);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> U[i] >> V[i], u = U[i], v = V[i];
g[v].emplace_back(make_pair(i + n, 4 * (i - 1)));
g[u].emplace_back(make_pair(i + n, 4 * (i - 1) + 1));
g[i + n].emplace_back(make_pair(u, 4 * (i - 1) + 2));
g[i + n].emplace_back(make_pair(v, 4 * (i - 1) + 3));
}
precalc(2000);
init();
int p = 0;
for (pii tmp : g[Mid]) dp[p][tmp.second][cnt[tmp.second][len]] = fac[cnt[tmp.second][len]];
for (int r = len - 1; r; r--, p ^= 1)
{
memset(dp[p ^ 1], 0, sizeof(dp[p ^ 1]));
for (int st = 0; st < 4 * (n - 1); st++)
{
int id = st / 4 + 1, ls, nw, op;
if (st % 4 == 0) nw = id + n, ls = V[id], op = 0;
else if (st % 4 == 1) nw = id + n, ls = U[id], op = 0;
else if (st % 4 == 2) nw = U[id], ls = id + n, op = 1;
else nw = V[id], ls = id + n, op = 1;
//转移1:反复横跳。此时枚举删去点数m作为新的可插入长度,剩下的直接插入前面即可。
//组合数:(cnt排列) * (cnt-m个插入l)
int nst = 4 * (id - 1) + 3 - (st % 4);
for (int l = 1; l <= n; l++)
for (int m = 1; m <= cnt[nst][r]; m++)
(dp[p ^ 1][nst][m] += dp[p][st][l] * Ch(l, cnt[nst][r] - m) % mod * fac[cnt[nst][r]] % mod) %= mod;
//转移2:继续向前。此时之前的点数直接并入l,作为新的可插入长度。
//组合数:(u点数排列) * (去u去v点数排列) * (去u去v点数插入l+1)
for (int l = 1; l <= n; l++)
for (pii tmp : g[nw])
{
int v = tmp.first;
if (v == ls) continue;
int t1 = cnt[st][r - 1];
int t2 = cnt[tmp.second][r] - cnt[st][r - 1];
if (l + t1 + t2 > n) continue;
(dp[p ^ 1][tmp.second][l + t1 + t2] += dp[p][st][l] * fac[t1] % mod * fac[t2] % mod * Ch(l + t1 + 1, t2) % mod) %= mod;
}
}
// for (int st = 0; st < 4 * (n - 1); st++, cout << "\n")
// for (int l = 1; l <= n; l++) cout << dp[p ^ 1][st][l] << " ";
// cout << "\n";
}
ll ans = 0;
for (int st = 0; st < 4 * (n - 1); st++)
for (int l = 1; l <= n; l++) (ans += dp[p][st][l]) % mod;
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 36396kb
input:
3 1 2 3 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 6ms
memory: 37660kb
input:
5 4 1 4 5 1 2 1 3
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 3ms
memory: 37440kb
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: 19ms
memory: 38496kb
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:
2795647739182
result:
wrong answer 1st numbers differ - expected: '748786623', found: '2795647739182'