QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379361 | #8568. Expected Diameter | ucup-team052# | AC ✓ | 4362ms | 148108kb | C++23 | 2.9kb | 2024-04-06 17:16:42 | 2024-04-06 17:16:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int md = 998244353;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
inline int mul(int x, int y) {
return 1ull * x * y % md;
}
inline int fpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1; x = mul(x, x);
}
return ans;
}
const int N = 2005;
int dp[N * 2][N], g[N * 2][N], s[N * 2][N], C[N][N], fac[N], inv[N], invv[N], dpp[N * 2][N];
int n, p1, p2, ans;
// e^f = g
// f'g = g'
int df[N], F[N], G[N * 2][N];
void exp(int *f, int *g) {
g[0] = 1;
for (int i = 1; i <= n; i++) df[i - 1] = mul(f[i], i);
for (int i = 1; i <= n; i++) {
__uint128_t sum = 0;
for (int j = 0; j <= i - 1; j++) {
sum += 1ull * df[j] * g[i - 1 - j];
}
g[i] = mul(sum % md, invv[i]);
}
}
int main() {
scanf("%d", &n);
fac[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
invv[i] = fpow(i, md - 2);
fac[i] = mul(fac[i - 1], i);
inv[i] = mul(inv[i - 1], invv[i]);
}
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
}
{
int x, y;
scanf("%d%d", &x, &y);
p1 = mul(x, fpow(y, md - 2));
p2 = sub(1, p1);
}
dpp[0][1] = 1;
dp[1][1] = p1; dp[2][1] = p2;
G[0][0] = 1;
for (int j = 1; j <= 2 * n; j++) {
for (int i = 1; i <= n; i++) {
s[j][i] = add(s[j - 1][i], dp[j][i]);
// fprintf(stderr, "dp[%d][%d] = %d\n", i, j, dp[j][i]);
}
for (int i = 1; i <= n; i++) F[i] = mul(s[j][i], inv[i]);
exp(F, G[j]);
for (int i = 0; i <= n; i++) {
G[j][i] = mul(G[j][i], fac[i]);
dpp[j][i + 1] = mul(sub(G[j][i], G[j - 1][i]), i + 1);
dp[j + 1][i + 1] = add(dp[j + 1][i + 1], mul(sub(G[j][i], G[j - 1][i]), mul(i + 1, p1)));
dp[j + 2][i + 1] = add(dp[j + 2][i + 1], mul(sub(G[j][i], G[j - 1][i]), mul(i + 1, p2)));
}
}
/*
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 2 * n; j++) {
if (dpp[j][i]) {
fprintf(stderr, "dpp[%d][%d] = %d\n", i, j, dpp[j][i]);
}
}
}
*/
for (int j = 0; j <= n; j++) {
for (int i = 0; i < n; i++) {
if (i > n - i) continue;
int res = mul(mul(dpp[j][i], dpp[j][n - i]), C[n][i]);
if (i == n - i) res = mul(res, (md + 1) / 2);
ans = add(ans, mul(res, mul(p1, j * 2 + 1)));
ans = add(ans, mul(res, mul(p2, j * 2 + 2)));
}
for (int i = 1; i < n; i++) {
int res = mul(mul(dpp[j][i], dpp[j + 1][n - i]), C[n][i]);
ans = add(ans, mul(res, mul(p2, j * 2 + 3)));
}
}
// printf("%d\n", ans);
for (int j = 1; j <= n * 2; j++) {
int res = dpp[j][n];
for (int i = 0; i < n; i++) {
res = sub(res, mul(mul(mul(G[j - 1][i], dp[j][n - i - 1]), C[n - 1][i]), n));
}
ans = add(ans, mul(res, j * 2));
}
ans = mul(ans, fpow(fpow(n, n - 2), md - 2));
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10232kb
input:
2 1 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9996kb
input:
3 2 3
output:
665496238
result:
ok 1 number(s): "665496238"
Test #3:
score: 0
Accepted
time: 4336ms
memory: 147828kb
input:
2000 1 2
output:
254870088
result:
ok 1 number(s): "254870088"
Test #4:
score: 0
Accepted
time: 4322ms
memory: 148108kb
input:
2000 1 3
output:
193693601
result:
ok 1 number(s): "193693601"
Test #5:
score: 0
Accepted
time: 4362ms
memory: 146056kb
input:
1999 188 211
output:
463395288
result:
ok 1 number(s): "463395288"
Test #6:
score: 0
Accepted
time: 4284ms
memory: 145580kb
input:
1990 470 818
output:
479264654
result:
ok 1 number(s): "479264654"
Test #7:
score: 0
Accepted
time: 560ms
memory: 80876kb
input:
1000 407 783
output:
20089106
result:
ok 1 number(s): "20089106"
Test #8:
score: 0
Accepted
time: 562ms
memory: 80668kb
input:
990 884 901
output:
94051884
result:
ok 1 number(s): "94051884"
Test #9:
score: 0
Accepted
time: 550ms
memory: 81280kb
input:
995 873 988
output:
209191626
result:
ok 1 number(s): "209191626"
Test #10:
score: 0
Accepted
time: 82ms
memory: 43360kb
input:
500 307 938
output:
603465152
result:
ok 1 number(s): "603465152"
Test #11:
score: 0
Accepted
time: 71ms
memory: 43992kb
input:
490 237 732
output:
402554558
result:
ok 1 number(s): "402554558"
Test #12:
score: 0
Accepted
time: 76ms
memory: 41776kb
input:
495 473 511
output:
833418554
result:
ok 1 number(s): "833418554"
Test #13:
score: 0
Accepted
time: 12ms
memory: 28380kb
input:
250 69 207
output:
786182422
result:
ok 1 number(s): "786182422"
Test #14:
score: 0
Accepted
time: 8ms
memory: 27984kb
input:
240 184 259
output:
473414786
result:
ok 1 number(s): "473414786"
Test #15:
score: 0
Accepted
time: 12ms
memory: 27868kb
input:
245 478 807
output:
312847415
result:
ok 1 number(s): "312847415"
Test #16:
score: 0
Accepted
time: 3ms
memory: 20176kb
input:
125 112 253
output:
31497383
result:
ok 1 number(s): "31497383"
Test #17:
score: 0
Accepted
time: 5ms
memory: 17484kb
input:
120 137 498
output:
923043504
result:
ok 1 number(s): "923043504"
Test #18:
score: 0
Accepted
time: 0ms
memory: 17680kb
input:
100 230 792
output:
203877027
result:
ok 1 number(s): "203877027"
Extra Test:
score: 0
Extra Test Passed