传送门

这题我在比赛的时候竟然没有想出来，真是……

这道题我们可以想一想怎么搞定获胜的概率p。

我们发现再怎么这个p都是搞不了的。所以我们可以积一下分，然后就可以不用去管p了。我们要做的就是求出一个关于p的多项式。

我们又发现，对于整体的期望，并不好直接表示出来（是可以表示出来的）。所以我们就想一想怎么去递推吧。

设f(i,j)表示赢了i场，输了j场的概率（一个关于p的多项式）。那么我们就可以列出一个式子：

然后，我们枚举所有的f(x,i)和所有的f(i,y)并求关于它们的从0到1的定积分。加起来就是我们的答案了！

#include <cstdio>

#include <cstring>

#include <cmath>

#define MAXN 45

struct Pol {

    double a[MAXN];

    Pol(){ memset(a, 0, sizeof a); }

    Pol operator * (const Pol&B) {

        Pol c; memset(c.a, 0, sizeof c.a);

        for(int i = 0; i < MAXN; ++ i)

            for(int j  = 0; j <= i; ++ j) {

                c.a[i] += a[i-j] * B.a[j];

            }

        return c;

    }

    Pol operator + (const Pol&B) {

        Pol c;

        for(int i = 0; i < MAXN; ++ i) c.a[i] = a[i] + B.a[i];

        return c;

    }

    void getPre() {//积分

        for(int i = MAXN-1; i > 0; -- i) a[i] = a[i-1]/i;

        a[0] = 0;

    }

    double Get_Ans() {

        getPre();

        double ans = 0;

        for(int i = 1; i < MAXN; ++ i) ans += a[i];

        return ans;

    }

}f[MAXN][MAXN], p, _p;

int n, m;

int main() {

    scanf("%d%d", &n, &m);

    f[0][0].a[0] = 1; p.a[1] = 1; _p.a[0] = 1; _p.a[1] = -1;

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

        for(int j = 0; j < m; ++ j) {

            if(i > 0) f[i][j] = f[i-1][j] * p;

            if(j > 0) f[i][j] = f[i][j] + (f[i][j-1] * _p);

        }

    double ans = 0;

    for(int i = 0; i < m; ++ i) {

        f[n][i] = f[n-1][i] * p;

        ans += f[n][i].Get_Ans() * n;

    }

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

        f[i][m] = f[i][m-1] * _p;

        ans += f[i][m].Get_Ans() * i;

    }

    printf("%lf\n", ans);

}