ZJUT 1317 擲飛盤 （高斯解期望問題）

題目：有m個人，圍成一個圈，有兩個飛盤，1/2的概率往左往右擲，最初兩個飛盤相隔n，問兩個飛盤到一個人手中的期望次數為多少。
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1317 
每一次擲飛盤，有4種方案，兩個都順時針，兩個都逆時針，一順一逆。
對於這4種方案，造成飛盤間隔的變化是有規律的  我們令E[i]表示間隔為i時到目標狀態的所需步數
那麼E[i]=(2*E[i]+E[i-2]+E[i+2])/4。其中E[0]是目標狀態為 0
E[n]為所求。
可以發現間隔的范圍是 0-m/2，如果大於m/2可以轉換一下。
一開始可能處理得非常麻煩，分了很多情況以及奇偶
不過可以直接轉換，如果出現負的則轉正，如果出現大於上界，則取另外一邊的。
開始的WA是因為沒有考慮到有一些狀態不可達，又忽視了這個重要的地方。
先搜索一遍，標記可以到達的狀態，並編號，然後對於這些狀態建立方程
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
#include<vector> 
#include<cmath> 
#define LL long long 
#define MOD 1000000007 
#define eps 1e-6 
#define zero(a)  fabs(a)<eps 
using namespace std; 
int n,m,num[105],cnt,tot; 
double a[105][105]; 
void debug(int n){ 
    for(int i=0;i<n;i++){ 
        for(int j=0;j<=n;j++) 
           printf("%.2f ",a[i][j]); 
        printf("\n"); 
    } 
} 
int get(int x){ 
    if(x<0) x=-x; 
    if(x>tot) x=m-x; 
    return x; 
} www.2cto.com
void dfs(int x){ 
    num[x]=cnt++; 
    int t=get(x-2); 
    if(num[t]==-1) dfs(t); 
    t=get(x+2); 
    if(num[t]==-1) dfs(t); 
} 
bool gauss(int n){ 
    int i,j; 
    for(i=0,j=0;i<n&&j<n;j++){ 
        int k; 
        for(k=i;k<n;k++) 
            if(!zero(a[k][j])) 
                break; 
        if(k<n){ 
            if(i!=k) 
            for(int r=j;r<=n;r++) swap(a[i][r],a[k][r]); 
            double tt=1/a[i][j]; 
            for(int r=j;r<=n;r++) 
                a[i][r]*=tt; 
            for(int r=0;r<n;r++) 
                if(r!=i){ 
                    for(int t=n;t>=j;t--) 
                        a[r][t]-=a[r][j]*a[i][t]; 
                } 
            i++; 
        } 
    } 
    for(int r=i;r<n;r++) 
        if(!zero(a[r][n])) 
            return false; 
    return true; 
} 
int main(){ 
    while(scanf("%d%d",&m,&n)!=EOF){ 
        if(n>m/2) n=m-n; 
        if(n==0){printf("0.00\n");continue;} 
        if(m%2==0&&n==1) {printf("INF\n");continue;} 
        tot=m/2; 
        memset(num,-1,sizeof(num)); 
        cnt=0; 
        dfs(n); 
        if(num[0]==-1) {printf("INF\n");continue;} 
        memset(a,0,sizeof(a)); 
        a[num[0]][num[0]]=1; 
        for(int i=1;i<=tot;i++){ 
            if(num[i]!=-1){ 
                int j=num[i]; 
                a[j][j]=-2;a[j][cnt]=-4; 
                int t=get(i-2); 
                a[j][num[t]]++; 
                t=get(i+2); 
                a[j][num[t]]++; 
            } 
        } 
       // debug(cnt); 
        if(gauss(cnt)){ 
            for(int i=0;i<cnt;i++) 
                if(zero(a[i][num[n]]-1)) 
                     printf("%.2f\n",a[i][cnt]); 
        } 
        else 
            puts("INF"); 
    } 
    return 0; 
}