【NOIP2012模拟10.31】擲骰子

題目

太郎和一隻免子正在玩一個擲骰子遊戲。有一個有N個格子的長條棋盤，太郎和兔子輪流擲一個有M面的骰子，骰子M面分别是1到M的數字.且擲到任意一面的機率是相同的.擲到幾.就往前走幾步.當誰走到第N格時，誰就獲勝了。遊戲中還有一個規則“反彈”.就是當一位選手要走到第N格外時.他就會後退(就像飛行棋進營一樣)。

假設現在一位追手在A格.當他擲出B時：


1.A+B<N，走到第A+B.絡，


2.A+B=N，走到第N格，獲勝。


3.A+B≥N，走到第(N-(A+B-N)格


現在太郎和兔子分别在第x和y格.接下來是太郎擲骰子，太郎想知道他赢得比賽的機率就多少。
           

分析

設 fi,j 表示太郎在i，兔子在j，太郎的勝率。我們從後往前轉移。

我們分四種情況：

、i+m<=n and j+m<=n
、i+m>n and j+m<=n
、i+m<=n and j+m>n
、i+m>n and j+m>n
           

why?

因為發現，當 i+m>n 時，i怎麼跳總是 i+m>n ，那麼就可以把它們當做同一種狀态。j也一樣。

情況一：i+m<=n and j+m<=n

因為i走到k的機率為 1m ，j走到l的機率也為 1m ，

那麼狀态(i,j)的勝率就是狀态(k,l)勝率的總和。

fi,j=1m2∑k=i+1i+m+1∑l=j+1j+m+1fk,l

情況二：i+m>n and j+m<=n

fi,j=(m−1)∑j+m+1l=j+1fi,lm2+1m

顯然i有 1m 的機率到達終點，而i有m種可能，又那麼既然已經算了到達終點的機率，那麼就不用在計算，是以乘以(m-1)。

情況三：i+m<=n and j+m>n

fi,j=(m−1)∑i+m+1k=i+1fk,jm2+x(如果i=n−m，x=1，否則x=0)m

同樣j有m種可能，但不能讓他到達終點，那麼就不用在計算，是以乘以(m-1)。

而當i在n-m這個位置時，i也有 1m 的機率到達終點，有可能出現狀态(n,n)，由于太郎是先手，是以算太郎赢，而前面有減去了j到達終點的情況，是以加上去。

情況四：i+m>n and j+m>n

要求i赢，是以

當i第一回合就走到了n，機率為 1m ，

當i第一回合沒有走到n，而j也不能走到n，在第二回合i走到了n機率為 1m（1−1m）2

如果在第二回合i還是沒有走到n，而j還是不能走到n，在第三回合i走到了n機率為 1m（1−1m）4

如此類推，

fi,j=limitn→∞1m+1m（1−1m）2+1m（1−1m）4+...+1m（1−1m）2n

=1m（1+（1−1m）2+（1−1m）4+...）+（1−1m）2n

等比數列求和

=1m1∗[1−(1−1m）2n]1−（1−1m）2

因為數列的公比小于1， [1−(1−1m）2n] 無限趨近于1，是以

=1m11−（1−1m）2

解得

fi,j=m2m−1

但是這樣是 O(n4) 的，用矩陣字尾和優化，變成 O(n2) 。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=;
const int mo=;
const int N=;
using namespace std;
double f[N][N],n,m,x,y;
double val(int x1,int y1,int x2,int y2)
{
    return f[x1][y1]-f[x1][y2]-f[x2][y1]+f[x2][y2];
}
int main()
{
    scanf("%lf%lf%lf%lf",&n,&m,&x,&y);
    for(int i=n;i>=;i--)
        for(int j=n;j>=;j--)
        {
            f[i][j]=f[i+][j]+f[i][j+]-f[i+][j+];
            if(i==n)
            {
                f[i][j]++;
                continue;
            }
            if(j==n) continue;
            if(i+m>n && j+m>n)
                f[i][j]+=m/(*m-);
            else
            if(i+m>n)
                f[i][j]+=val(i,j+,i+,j+m+)*(m-)/m/m+/m;
            else
            if(j+m>n)
                f[i][j]+=(m-)*val(i+,j,i++m,j+)/m/m+(i==n-m)/m/m;
            else
                f[i][j]+=val(i+,j+,i+m+,j+m+)/(m*m);

        }
    printf("%.6lf",val(x,y,x+,y+));
}