QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379353 | #8568. Expected Diameter | ucup-team052# | TL | 1ms | 10212kb | C++23 | 2.9kb | 2024-04-06 17:14:39 | 2024-04-06 17:14:41 |
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][N];
int n, p1, p2, ans;
// e^f = g
// f'g = g'
int df[N], F[N], G[N][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: 10028kb
input:
2 1 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 1ms
memory: 10212kb
input:
3 2 3
output:
665496238
result:
ok 1 number(s): "665496238"
Test #3:
score: -100
Time Limit Exceeded
input:
2000 1 2