概率 方程组 递推

首先，需要计算单局Alice获胜的概率p.

方法1

这个由于l,r,L,R都是非常小的范围，所以，直接枚举每一个点，统计获胜点和失败点的个数即可求得。

方法2

如果l,r,L,R并不是100以内，那么需要通过皮克定理，线性规划，计算获胜区域内的整点数目和失败区域的整点数目。l和L的大小关系3种，同理r和R也是三种，共9种情况。当然，可以通过交换x和y以及仔细观察发现可以合并的情况。

其次，计算题目要求的概率

此时，问题可以表述成，已知A为n，B为m，每次，A有p的概率从B赢1点，否则，(1-p)的概率输一点。当一方为0游戏结束，问最终结束的状态是A有n+m的概率是多少。
我们有(u,v)表示A有u个，B有v个的状态。显然游戏结束状态只有两种，我们要求的是最终状态为的概率。
显然不论什么状态都有.因此，我们只需确定第一维的即确定了一个状态。
令表示当前状态是，最终状态变成的概率。
显然有.
对于,有方程.
因此，一共有个方程，未知数一共有个，然后都是一次方程。可解。
当然，没有必要上高斯消元解线性方程组，我们稍微手动解一下方程。
我们不妨将都用表示出来，可以发现都可以表示成的形式。
不难发现，。
之后，再将代入方程，解出，与进行对比，不难发现的递推式: .
故.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read()
{
    ll x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
        f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

void write(ll a)
{
    if (a < 0)
    {
        putchar('-');
        a = -a;
    }
    if (a >= 10)
    {
        write(a / 10);
    }
    putchar(a % 10 + '0');
}

void writeln(ll a,ll c='\n') {
    write(a);putchar(c);
}

double cal_p(ll l, ll r, ll L, ll R) {
    int a = 0,b = 0;
    for (ll i = l; i <= r; ++i)
        for (ll j = L; j <= R; ++j) {
            if (i>j) ++a;
            if (i<j) ++b;
        }
    return (1.0*a)/double(a+b);
}

double cal(ll a, ll n, double p) {
    vector<double>k(n);
    k[1] = p;
    for (int i = 2; i < n; ++i)
        k[i] = p/(1-(1-p)*k[i-1]);
#ifdef debugmode
    for (int i = 1; i < n; ++i)
        printf("%.05lf   ",k[i]);
    putchar('\n');
#else
#endif
    auto ans = double(1);
    for (int i = a; i < n; ++i)
        ans *= k[i];
    return ans;
}

int main()
{

    ll n,l,r,m,L,R;
    n = read(); l = read(); r = read();
    m = read(); L = read(); R = read();
    if (n == 0) {
        puts("0.00000");
        return 0;
    } else if (m == 0) {
        puts("1.00000");
        return 0;
    }
    auto p = cal_p(l,r,L,R);
#ifdef debugmode
    cout<<p<<endl;
#else
#endif
    auto q = 1-p;
    auto a = p*n;
    auto b = q*m;
    auto ans = cal(n,n+m,p);
    printf("%.5lf\n",ans);
    return 0;
}