【题解】担心

区间DP + 组合计数

设\(f(i, j)\)为只考虑\([i, j]\)段，且\(i,j\)能够相遇的概率。

特别地，设\(f(0, i)\)为\(i\)能打败左边所有人的概率，\(f(i, n+1)\)为\(i\)能打败右边所有人的概率。

转移只需要枚举中间点\(k\)，考虑最后剩下三个人\((i, k, j)\)，有一半概率抽到\((i, k)\)，一半概率抽到\((k, j)\)，计算概率即可。a

关键在于在到达最终状态\((i, k, j)\)之前，要保证\((i, k)\)和\((k, j)\)不能被选中对决，因此要计算概率并乘上去。

设\(k-i+1=n, j-k+1=m\)，则能达到最终状态的概率为：
\[ \dfrac{(n-1)!(m-1)! \binom{n+m-4}{n-2}}{\dfrac{(n+m-2)!}{2}} \]
其中\((n-1)!\)是\(n-1\)选\(n-2\)的排列

\(\dfrac{(n+m-2)!}{2}\)是\((n+m-2)\)选\(n+m-4\)的排列（总方案数）

即先内部排列，最后再整体可重排列。

对于\(f(0, i)\)和\(f(i, n+1)\)类似。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

const int p = 998244353, N = 505, inv2 = 499122177;
inline int add(int x, int y){return x+y>=p ? x+y-p : x+y;}
inline int sub(int x, int y){return x-y<0 ? x-y+p :x-y;}
inline int mul(int x, int y){return 1LL * x * y % p;}
inline int power(int x, int y){
    int res = 1;
    for(; y; y>>=1, x = mul(x, x)) if(y & 1) res = mul(res, x);
    return res;
}

int fac[N], ifac[N];
void preBinom(int n){
    fac[0] = fac[1] = 1;
    for(int i=2; i<=n; i++) fac[i] = mul(fac[i-1], i);
    ifac[n] = power(fac[n], p - 2);
    for(int i=n-1; i>=0; i--) ifac[i] = mul(ifac[i+1], i+1);
}
int C(int n, int m){return mul(fac[n], mul(ifac[m], ifac[n-m]));}
int F(int n, int m){ // 左右两边分别为n,m个元素
    return mul(mul(mul(fac[n-1], fac[m-1]), C(n+m-4, n-2)), mul(ifac[n+m-2], 2));
}

int a[N];
int Pr[N][N], f[N][N];

int main(){
    int n, pos;
    scanf("%d%d", &n, &pos);
    preBinom(n+3);
    for(int i=1; i<=n; i++) scanf("%d", a + i), f[i-1][i] = 1;
    f[n][n+1] = 1;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++){
            Pr[i][j] = mul(a[i] % p, power((a[i] + a[j]) % p, p - 2));
            Pr[j][i] = sub(1, Pr[i][j]);
        }
    for(int len=2; len<=n; len++){
        for(int i=1; i<len; i++) f[0][len] = add(f[0][len], 
            mul(
                mul(mul(f[0][i], f[i][len]), Pr[len][i]),
                mul(mul(mul(fac[i-1], fac[len-i]), C(len-2, i-1)), ifac[len-1])
            )
        );
        int now = n + 1 - len;
        for(int i=n+2-len; i<=n; i++){
            f[n+1-len][n+1] = add(f[n+1-len][n+1],
                mul(
                    mul(mul(f[n+1-len][i], f[i][n+1]), Pr[n+1-len][i]),
                    mul(mul(mul(fac[i-now], fac[n-i]), C(n-1-now, i-now-1)), ifac[n-now])
                )
            );
        }
        for(int i=1; i+len<=n; i++){
            int j = i + len;
            for(int k=i+1; k<j; k++)
                f[i][j] = add(f[i][j],
                    mul(mul(
                        mul(inv2, add(Pr[i][k], Pr[j][k])),
                        mul(f[i][k], f[k][j])),
                        F(k-i+1, j-k+1)
                    )
                );
        }
    }
    printf("%d\n", mul(f[0][pos], f[pos][n+1]));
    return 0;
}

【题解】担心

原文：https://www.cnblogs.com/RiverHamster/p/sol-oj4043.html