QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379361#8568. Expected Diameterucup-team052#AC ✓4362ms148108kbC++232.9kb2024-04-06 17:16:422024-04-06 17:16:43

Judging History

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

  • [2024-04-06 17:16:43]
  • 评测
  • 测评结果:AC
  • 用时:4362ms
  • 内存:148108kb
  • [2024-04-06 17:16:42]
  • 提交

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