Description
太郎和一隻免子正在玩一個擲骰子遊戲。有一個有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格.接下來是太郎擲骰子，太郎想知道他赢得比賽的機率就多少。
100%的資料.10≤n≤ 2000，1≤m,x,y≤n-1
Analysis
很好的一道題，2^1024個好評，推薦大家做做。
初二一群人水法水過，暴力走15000步遞推算答案卡精度卡時間竟然給卡過了？！無力吐槽。（infleaking同學（不是vfleaking神犇啊（%%%），大家不要看錯了）還高舉“能過的方法就是好方法”、“水法也是好方法”的旗幟。。。）
好了，扯了這麼多，這些個人見解到時候在集訓總結裡寫吧，回到正題。
DP
設 f[i][j] 表示A在i，B在j，A先走并獲勝的機率。
邊界的話如果 i=n ，顯然 f[i][j]=1
如果 j=n ，顯然 f[i][j]=0
有人要問了，如果 i=j=n ， f[i][j]=?
看看 f 的定義，由于目前是A走，是以一步之前是B走，兩步之前是A走，是以A在兩步之前就到達了n，是以 f[n][n]=1
那麼，剩下的就是轉移了。
我們分類讨論。
Case 1 : i<=n-m，j<=n-m
這部分沒什麼限制，直接dp
f[i][j]=∑i′=i+1i+m∑j′=j+1j+mf[i′][j′]∗1m2
Case 2：i>n-m，j>n-m
他們一旦走超過n-m，因為有反彈，他們的位置始終會在區間 [n−m+1,n] 内。
且除非有一個人走到了 n ，他們可能無窮地走下去。
這段區間内，所有點走到終點的機率都是1m。
那A先走且獲勝的機率就是
limn→+∞∑i=0n(1−1m)2i∗1m
這就是個等比數列嘛，上求和公式
=1m∗1∗(1−1m)+∞1−(1−1m)2
中間過程自己化簡，最後就是
=m2m−1
Case 3 : i>n-m，j<=n-m
i 隻有1種可能上次從n轉移過來，i共有m種可能，同時 j 也有m種取值，總共有 m2 種可能情況，區間内所有點都可視為一樣的。
是以
f[i][j]=(m−1)∗(∑j+mj′=j+1f[i][j′])+mm2
Case 4 : i<=n-m，j>n-m
類似Case3
f[i][j]=(m−1)∗(∑i+mi′=i+1f[i′][j])+(i==n−m)m2
若 i=n−m ，當 i′=j=n 時機率為1
當然，dp可以累加到二維字首和上，這樣單次狀态轉移就不需要 O(n2) 的時間。
Code
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
typedef double db;
const int N=;
db sum[N][N];
db S(int x1,int y1,int x2,int y2)
{
return sum[x1][y1]-sum[x1][y2]-sum[x2][y1]+sum[x2][y2];
}
int main()
{
int n,m,x,y;
scanf("%d %d %d %d",&n,&m,&x,&y);
db t=m*/(m+m-);
fd(i,n,)
fd(j,n,)
{
sum[i][j]=sum[i+][j]+sum[i][j+]-sum[i+][j+];
if(i==n)
{
sum[i][j]++;
continue;
}
if(j==n) continue;
if(i>n-m && j>n-m) sum[i][j]+=t;
else
if(i>n-m) sum[i][j]+=S(i,j+,i+,j+m+)*(m-)/(m*m)+/m;
else
if(j>n-m) sum[i][j]+=(S(i+,j,i+m+,j+)*(m-)+(i==n-m))/(m*m);
else sum[i][j]+=S(i+,j+,i+m+,j+m+)/(m*m);
}
printf("%.6lf",S(x,y,x+,y+));
return ;
}