QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379245#8568. Expected Diameterucup_team_qiuly#AC ✓4753ms45448kbC++145.8kb2024-04-06 16:45:272024-04-06 16:45:27

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 16:45:27]
  • 评测
  • 测评结果:AC
  • 用时:4753ms
  • 内存:45448kb
  • [2024-04-06 16:45:27]
  • 提交

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