hdu 1204 糖果大戰 (Markov Chains求期望)

糖果大戰

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2336 Accepted Submission(s): 797


Problem Description 生日Party結束的那天晚上，剩下了一些糖果，Gandon想把所有的都統統拿走，Speakless於是說：“可以是可以，不過我們來玩24點，你不是已經拿到了一些糖果了嗎？這樣，如果誰贏一局，就拿走對方一顆糖，直到拿完對方所有的糖為止。”如果誰能算出來而對方算不出來，誰就贏，但是如果雙方都能算出或者都不能，就算平局，不會有任何糖果的得失。
Speakless是個喜歡提前想問題的人，既然他發起了這場糖果大戰，就自然很想贏啦（不然可就要精光了-_-）。現在他需要你的幫忙，給你他每局贏的概率和Gardon每局贏的概率，請你給出他可能獲得這場大戰勝利的概率。

Input 每行有四個數，Speakless手上的糖果數N、Gardon手上的糖果數M(0<=N,M<=50)、一局Speakless能解答出來的概率p、一個問題Gardon能解答出來的概率q(0<=p,q<=1)。

Output 每行一個數，表示Speakless能贏的概率（用百分比計算，保留到小數點後2位）。

Sample Input

50 50 0.5 0.5
10 10 0.51 0.5
50 50 0.51 0.5

Sample Output

0.50
0.60
0.88

用f[i]表示Speakless有i顆糖果的時贏的概率，則f[i]=p(1-q)*f[i+1]+q(1-p)*f[i-1]+(1-p*(1-q)-q*(1-p))*f[i]; 這個方程表示當前狀態贏的期望等於當前狀態能到達的所有狀態贏的期望的和。化簡得， (f[i+1]-f[i-1])*p*(1-q)=f[i]-f[i-1]*(q*(1-p));
令k=(q*(1-p))/(p*(1-q));
設f[i+1]-f[i]= (f[i]-f[i-1])*k;

已知 f[0]=0;f[n+m]=1; （必輸和必贏）

f[1]-f[0]=f[1]; f[2]-f[1]=(f[1])*k; f[3]-f[2]=(f[2]-f[1])*k=f[1]*k^2; ... f[n]-f[n-1]=(f[n-1]-f[n-1])*k=f[1]*k^(n-1); 對數列求和，得 f[n]=(1-k^n)/(1-k); f[n+m]=(1-k^(n+m))/(1-k)=1;
則f[n]=f[n]/f[n+m]=(1-k^n)/(1-k^(n+m));

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define N 25
const int M=256;
const double eps=1e-4;

int main()
{
    int n,m,n1,n2,i;
    double k,s,p,q;
    while(~scanf("%d%d%lf%lf",&n,&m,&p,&q))
    {
        if(m==0)
            s=1;
        else if(n==0||p==0||q==1)
            s=0;
        else
        {
            k=q*(1-p)/p/(1-q);
            if(fabs(k-1.0)