@codeforces - 913F@ Strongly Connected Tournament

@description@
@solution@
@accepted code@
@details@

@description@

n 个选手参加了一场竞赛，这场竞赛的规则如下：

1.一开始，所有选手两两之间独立进行比赛（没有平局）。

2.主办方将胜者向败者连边形成 n 个点的竞赛图。

3.主办方对这个竞赛图进行强连通分量缩点。

4.每一个强连通分量内部的选手重复步骤 1~3，直到每一个强连通分量内只剩一个选手。

现已知当 i < j 时，选手 i 战胜选手 j 的概率是 p，请计算比赛次数的期望。

Input‘

第一行包含一个整数 n (2 ≤ n ≤ 2000) — 表示玩家个数。

第二行包含两个整数 a 和 b (1 ≤ a < b ≤ 100) — 表示概率 p = a/b。

Output

输出一行一个整数表示期望，对 998244353 取模。

Examples

Input

3

1 2

Output

4

Input

3

4 6

Output

142606340

Input

4

1 2

Output

598946623

Note

第一组样例答案是 4；

第二组样例答案是 27/7；

第三组样例答案是 56/5。

@solution@

可以发现题目给定的过程其实就是个求解子问题的过程，可以使用 dp。

考虑最暴力的解法：枚举每条边的定向，计算概率与此时的强连通分量，进行 dp 的转移。注意可以转移到自己，概率期望 dp 套路（指转移方程移项）即可。

我们发现，如果要求解自己转移到自己的概率，实际上是求 n 个点连成强连通分量的概率 g[n]。

先一步步来，考虑怎么求这个概率，可以使用套路容斥。

即假如 n 个点连不成强连通分量，我们就枚举拓扑序最前面的强连通分量大小 s。

令 f[n][s] 表示 n 个点的图选出 s 个点使得 s 个点与剩下 n-s 个点之间的连边总是 s 个点连过去的概率，则这个时候出现这种局面的概率为 g[s]*f[n][s]，最后 g[n] = 1 - ∑g[s]*f[n][s]。

现考虑怎么求 f[n][s]，可以做类似背包 dp 的方法。

假如加入的第 n 个点不在 s 个点之中，则从 f[n-1][s] 转移过来，s 个点要全部向点 n 连边，所以概率为 p^s。

假如加入的第 n 个点在 s 个点之中，则从 f[n-1][s-1] 转移过来，点 n 要向除了选出来的 s 个点的其他点连边，所以概率为 (1-p)^(n-s)。

现在回到一开始的 dp，考虑不是转移到自己的时候（即没有形成强连通）。假如缩点后的图为 A1->A2->...->Am，则对应的概率为 g[A1]*f[n][A1] + g[A2]*f[n-A1][A2] + ...，对应的权值为 dp[A1] + dp[A2] + ...。

我们怎么优化这个 dp 呢？不妨令 h[n] 表示将 n 个点划分成若干强连通分量对应的期望（注意不同于 dp 数组的定义，h 只是“划分”，并没有计算划分出来的强连通分量两两之间的贡献）（划分出来的强连通可以只有一个）。

h 的转移可以通过枚举拓扑序最前的强连通（类似于上面的容斥）。dp 的转移与 h 类似，也是枚举拓扑序最前的强连通。

@accepted code@

#include<cstdio>

const int MAXN = 2000;

const int MOD = 998244353;

int pow_mod(int b, int p) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%MOD;

		b = 1LL*b*b%MOD;

		p >>= 1;

	}

	return ret;

}

int n, a, b, p1[MAXN + 5], p2[MAXN + 5];

int f[MAXN + 5][MAXN + 5], g[MAXN + 5];

int dp[MAXN + 5], h[MAXN + 5];

int main() {

	scanf("%d%d%d", &n, &a, &b);

	p1[0] = 1, p1[1] = 1LL*a*pow_mod(b, MOD-2)%MOD;

	p2[0] = 1, p2[1] = (MOD + 1 - p1[1])%MOD;

	for(int i=2;i<=n;i++)

		p1[i] = 1LL*p1[i-1]*p1[1]%MOD, p2[i] = 1LL*p2[i-1]*p2[1]%MOD;

	f[1][1] = 1;

	for(int i=2;i<=n;i++) {

		f[i][1] = (1LL*f[i-1][1]*p1[1]%MOD + p2[i-1])%MOD;

		for(int j=2;j<=i;j++)

			f[i][j] = (1LL*f[i-1][j]*p1[j]%MOD + 1LL*f[i-1][j-1]*p2[i-j]%MOD)%MOD;

	}

	for(int i=1;i<=n;i++) {

		g[i] = 1;

		for(int j=1;j<i;j++)

			g[i] = (g[i] + MOD - 1LL*g[j]*f[i][j]%MOD)%MOD;

	}

	h[1] = dp[1] = 0;

	for(int i=2;i<=n;i++) {

		for(int j=1;j<i;j++)

			h[i] = (h[i] + 1LL*g[j]*f[i][j]%MOD*(dp[j] + h[i-j])%MOD)%MOD;

		dp[i] = 1LL*(h[i] + 1LL*i*(i-1)/2%MOD)*pow_mod((1 + MOD - g[i])%MOD, MOD-2)%MOD;

		h[i] = (h[i] + 1LL*g[i]*dp[i]%MOD)%MOD;

	}

	printf("%d\n", dp[n]);

}

@details@

一开始把边的数量（即原题目中比赛的数量）统计成点的数量，手玩样例还以为是样例的问题。。。

巴特西

@codeforces - 913F@ Strongly Connected Tournament

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章