@codeforces - 913F@ Strongly Connected Tournament

谁借莪１个温暖的怀抱￠ 2023-06-01 12:59 10阅读 0赞

*  @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@ ##

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

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11382038.html