首先,需要计算单局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; }