QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379245 | #8568. Expected Diameter | ucup_team_qiuly# | AC ✓ | 4753ms | 45448kb | C++14 | 5.8kb | 2024-04-06 16:45:27 | 2024-04-06 16:45:27 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
x = 0, _f = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
const int mod = 998244353;
const int inv2 = (mod + 1) >> 1;
inline int mul (int x, int y) { return 1ll * x * y % mod; }
inline int qpow (int x, int y, int r = 1) { for ( ; y; y >>= 1, x = mul (x, x)) if (y & 1) r = mul (r, x); return r; }
inline void sub (int &x, int y) { x -= y; if (x < 0) x += mod; }
inline void pls (int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline int dec (int x, int y) { x -= y; if (x < 0) x += mod; return x; }
inline int add (int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
// poly
namespace Poly {
const int Lim = 1 << 20;
#define Lep(i, l, r) for (int i = (l), i##_end = (r); i < i##_end; ++ i)
int iv[Lim | 5], w[Lim | 5], _g[Lim | 5];
inline void init_w () {
* w = 1, w[1 << 20] = qpow (3, (mod - 1) >> 22);
rep (i, 20, 1) w[1 << i - 1] = mul (w[1 << i], w[1 << i]);
Lep (i, 1, Lim) w[i] = mul (w[i & (i - 1)], w[i & ( - i)]);
iv[1] = 1; lep (i, 2, Lim) iv[i] = mul (iv[mod % i], mod - mod / i);
}
struct poly {
int lim; vector <int> a;
inline int size () { return (int) a.size (); }
inline int & operator [] (const int &x) { return a[x]; }
inline void clear () { vector <int> ().swap (a); }
inline void resize (const int &x) { a.resize (lim = x); }
poly (int n = 0) { resize (lim = n); }
poly (const vector <int> &o) { a = o, lim = size (); }
poly (const poly &o) { a = o.a, lim = size (); }
inline void dif () {
int s, p, * tw, * tg, * pg;
for (p = lim >> 1; p; p >>= 1)
for (tg = _g, tw = w; tg != _g + lim; tg += p << 1, ++ tw)
for (pg = tg; pg != tg + p; ++ pg)
s = mul (pg[p], * tw), pg[p] = dec (* pg, s), pls ( * pg, s);
}
inline void dit () {
int s, p, * tw, * tg, * pg;
for (p = 1; p < lim; p <<= 1)
for (tg = _g, tw = w; tg != _g + lim; tg += p << 1, ++ tw)
for (pg = tg; pg != tg + p; ++ pg)
s = pg[p], pg[p] = mul ( * pg + mod - s, * tw), pls ( * pg, s);
}
inline void dft () {
copy_n (a.begin (), lim, _g), dif ();
Lep (i, 0, lim) a[i] = _g[i];
}
inline void idft () {
copy_n (a.begin (), lim, _g), dit ();
for (int iv = mod - (mod - 1) / lim, i = 0; i < lim; ++ i) a[i] = mul (_g[i], iv);
reverse ( ++ a.begin (), a.end ());
}
inline friend poly operator * (poly a, poly b) {
int n = a.size (), m = b.size (), lim;
for (lim = 1; lim < n + m - 1; lim <<= 1);
a.resize (lim), a.dft (), b.resize (lim), b.dft ();
Lep (i, 0, lim) a[i] = mul (a[i], b[i]);
return a.idft (), a.resize (n + m - 1), a;
}
inline poly inv () {
poly b (1), c; b[0] = qpow (a[0], mod - 2);
for (int i = 1; i < lim; i <<= 1) {
c = a, c.resize (i << 1);
c.resize (i << 2), c.dft (), b.resize (i << 2), b.dft ();
Lep (j, 0, i << 2) b[j] = mul (b[j], dec (2, mul (b[j], c[j])));
b.idft (), b.resize (i << 1);
}
return b;
}
inline poly inter () {
poly ret (lim + 1);
Lep (i, 0, lim) ret[i + 1] = mul (a[i], iv[i + 1]);
return ret;
}
inline poly deriv () {
poly ret (lim - 1);
Lep (i, 1, lim) ret[i - 1] = mul (a[i], i);
return ret;
}
inline poly ln () {
poly ret = (deriv () * inv ()).inter ();
return ret.resize (lim), ret;
}
inline poly exp () {
poly b (1), c; b[0] = 1;
for (int i = 1; i < lim; i <<= 1) {
c = b, c.resize (i << 1), c = c.ln ();
Lep (j, 0, min (lim, i << 1)) sub (c[j], a[j] + (j == 0));
Lep (j, 0, i << 1) c[j] = mod - c[j]; b = b * c, b.resize (i << 1);
}
return b;
}
};
}
using Poly :: init_w;
using Poly :: poly;
//
signed main () {
init_w ();
int n, x, y;
IN (n), IN (x), IN (y);
int p1 = mul (x, qpow (y, mod - 2)), p2 = 1 + mod - p1;
vector <int> fac (n + 1), ifac (n + 1); {
fac[0] = 1; lep (i, 1, n) fac[i] = mul (fac[i - 1], i);
ifac[n] = qpow (fac[n], mod - 2); rep (i, n, 1) ifac[i - 1] = mul (ifac[i], i);
}
vector <poly> h (2 * (n - 1) + 1, poly (n + 1));
h[0][1] = 1;
lep (x, 1, 2 * (n - 1)) {
poly sub (n + 1);
if (x >= 1) lep (i, 0, n) pls (sub[i], mul (h[x - 1][i], p1));
if (x >= 2) lep (i, 0, n) pls (sub[i], mul (h[x - 2][i], p2));
sub = sub.exp ();
lep (i, 1, n) h[x][i] = sub[i - 1];
}
auto hp = [&] (int x, int y) {
return add (h[x][y], (x ? mod - h[x - 1][y] : 0));
};
int ans = 0;
lep (dia, 1, 2 * (n - 1)) {
int x = dia / 2, ret = 0;
if (! (dia & 1)) { // point
pls (ret, hp (x, n));
poly only (n + 1);
if (x >= 1) lep (i, 0, n) pls (only[i], mul (p1, hp (x - 1, i)));
if (x >= 2) lep (i, 0, n) pls (only[i], mul (p2, hp (x - 2, i)));
only = only * h[x - 1];
pls (ret, mod - only[n]);
} { // edge
if (dia & 1) { // edge 1
int sum = 0;
lep (i, 1, n - 1) pls (sum, mul (hp (x, i), hp (x, n - i)));
pls (ret, mul (p1, mul (sum, inv2)));
}
if (dia >= 2 && ! (dia & 1)) { // edge 2 & middle
int sum = 0;
lep (i, 1, n - 1) pls (sum, mul (hp (x - 1, i), hp (x - 1, n - i)));
pls (ret, mul (p2, mul (sum, inv2)));
}
if (dia >= 3 && (dia & 1)) { // edge 2 & quad
int sum = 0;
lep (i, 1, n - 1) pls (sum, mul (hp (x, i), hp (x - 1, n - i)));
pls (ret, mul (p2, sum));
}
}
pls (ans, mul (ret, dia));
}
ans = mul (ans, fac[n]);
ans = mul (ans, qpow (qpow (n, n - 2), mod - 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: 12628kb
input:
2 1 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 5ms
memory: 13896kb
input:
3 2 3
output:
665496238
result:
ok 1 number(s): "665496238"
Test #3:
score: 0
Accepted
time: 4753ms
memory: 44464kb
input:
2000 1 2
output:
254870088
result:
ok 1 number(s): "254870088"
Test #4:
score: 0
Accepted
time: 4742ms
memory: 45448kb
input:
2000 1 3
output:
193693601
result:
ok 1 number(s): "193693601"
Test #5:
score: 0
Accepted
time: 4731ms
memory: 44084kb
input:
1999 188 211
output:
463395288
result:
ok 1 number(s): "463395288"
Test #6:
score: 0
Accepted
time: 4736ms
memory: 43496kb
input:
1990 470 818
output:
479264654
result:
ok 1 number(s): "479264654"
Test #7:
score: 0
Accepted
time: 1125ms
memory: 21108kb
input:
1000 407 783
output:
20089106
result:
ok 1 number(s): "20089106"
Test #8:
score: 0
Accepted
time: 1099ms
memory: 21496kb
input:
990 884 901
output:
94051884
result:
ok 1 number(s): "94051884"
Test #9:
score: 0
Accepted
time: 1106ms
memory: 21188kb
input:
995 873 988
output:
209191626
result:
ok 1 number(s): "209191626"
Test #10:
score: 0
Accepted
time: 261ms
memory: 14140kb
input:
500 307 938
output:
603465152
result:
ok 1 number(s): "603465152"
Test #11:
score: 0
Accepted
time: 260ms
memory: 16272kb
input:
490 237 732
output:
402554558
result:
ok 1 number(s): "402554558"
Test #12:
score: 0
Accepted
time: 264ms
memory: 14780kb
input:
495 473 511
output:
833418554
result:
ok 1 number(s): "833418554"
Test #13:
score: 0
Accepted
time: 69ms
memory: 13812kb
input:
250 69 207
output:
786182422
result:
ok 1 number(s): "786182422"
Test #14:
score: 0
Accepted
time: 62ms
memory: 13632kb
input:
240 184 259
output:
473414786
result:
ok 1 number(s): "473414786"
Test #15:
score: 0
Accepted
time: 67ms
memory: 12572kb
input:
245 478 807
output:
312847415
result:
ok 1 number(s): "312847415"
Test #16:
score: 0
Accepted
time: 22ms
memory: 12596kb
input:
125 112 253
output:
31497383
result:
ok 1 number(s): "31497383"
Test #17:
score: 0
Accepted
time: 18ms
memory: 13832kb
input:
120 137 498
output:
923043504
result:
ok 1 number(s): "923043504"
Test #18:
score: 0
Accepted
time: 15ms
memory: 12500kb
input:
100 230 792
output:
203877027
result:
ok 1 number(s): "203877027"
Extra Test:
score: 0
Extra Test Passed