QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379353#8568. Expected Diameterucup-team052#TL 1ms10212kbC++232.9kb2024-04-06 17:14:392024-04-06 17:14:41

Judging History

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

  • [2024-04-06 17:14:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:10212kb
  • [2024-04-06 17:14:39]
  • 提交

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

output:


result: