令res[i][s1][k]表示第i行状态为s1，前i行摆放棋子的个数为k的方案个数；

res[i][s1][k]=∑res[i-1][s2][k-inum]; inum表示第i行摆放的棋子个数，s1,s2表示第i行和第i-1行的状态，两种状态能够相容。

#include
     
      #include
      
       #include
       
        using namespace std;#define lld long long lld res[11][1025][101];int n,m;int init(int j,int state,int inum,int b){	if(j>=n)	{	    res[1][state][inum]=1;		return 0;	}	if(b==0)	{		init(j+1,(state<<1)+1,inum+1,1);		init(j+1,state<<1,inum,0);	}	if(b==1)	{		init(j+1,state<<1,inum,0);	}    return 0;}int dfs(int i,int j,int s1,int s2,int inum,int b)//b表示当前位置的摆放对后一列的影响{	if(j>=n)	{		for(int l=0;l<=m;l++)			if(res[i-1][s2][l]) res[i][s1][l+inum]+=res[i-1][s2][l];        return 0;	}	if(b==0) 	{		dfs(i,j+1,(s1<<1)+1,s2<<1,inum+1,1);		dfs(i,j+1,s1<<1,s2<<1,inum,0);		dfs(i,j+1,s1<<1,(s2<<1)+1,inum,1);	}	if(b==1)	{	    dfs(i,j+1,s1<<1,s2<<1,inum,0);	}	return 0;}int main(){	int i;	lld sum;	while(scanf("%d %d",&n,&m)!=EOF)	{		memset(res,0,sizeof(res));		init(0,0,0,0);		for(i=2;i<=n;i++)			dfs(i,0,0,0,0,0);		sum=0;		for(i=0;i<(1<