转移方程很显然。

因为是多段图模型，所以可以滚动数组优化一维空间。

#include
     
      #include
      
       using namespace std;int m,K,n,p;bool zaw[1010][30010];double f[2][30010];int main(){	int x,y;	bool flag=1;	scanf("%d%d%d%d",&m,&K,&n,&p);	for(int i=1;i<=K;++i){		scanf("%d%d",&x,&y);		if(y<=n){			zaw[y][x]=1;			flag=0;		}	}	if(m==1){		if(!flag){			puts("0.000000");		}		else{			puts("1.000000");		}		return 0;	}	bool cur=0;	f[cur][p]=1;	for(int i=1;i<=n;++i){		cur^=1;		memset(f[cur],0,sizeof(f[cur]));		for(int k=1;k<=2;++k){			if(!zaw[i-1][1]){				f[cur][k]+=f[cur^1][1]/2.0;			}		}		for(int k=m-1;k<=m;++k){			if(!zaw[i-1][m]){				f[cur][k]+=f[cur^1][m]/2.0;			}		}		for(int j=2;j