原题见于acwing291

下面是蒟蒻的代码与思路

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=15;
int n,m;
int f[N][(1<<N)];//前i-1列已经摆放好 且从i-1列延伸到第i列的长条状态为j 的方案数 因此我们将横条的状态进行状压 
signed main()
{
	while(1)
	{
		scanf("%lld%lld",&n,&m);  
		if( !n && !m ) return 0;  
		memset(f,0,sizeof f);
        f[0][0]=1;
		for( int i=1 ; i<=m ; ++i ) //阶段 枚举前i列 
		{                         
			for( int j = 0 ; j < (1<<n) ; ++j ) //状态 
			{                     
                f[i][j]=0;        
				for( int k = 0 ; k < (1<<n) ; ++k ) // 决策 
				{                 
                    int res=0;
                    int t=k|j;
                    bool flag=0;
                    do
                    {
                        if(!(t&1)) res++; 
                        else 
                        {
                            if(res&1) // 连续的空位为偶数 否侧无法填完  
                            { 
                                flag=1; 
                                break; 
                            } 
                            res=0; 
                        } 
                        t>>=1; 
                    } while(t);          
                    if(res&1) continue;  
                    if(flag) continue;   
					if( ( j & k ) == 0 ) //第i-2延伸的与i-1延伸的不重复
                    {                    
                        // printf("J:%lld K:%lld I:%lld \n",j,k,i);  
                        f[i][j]+=f[i-1][k] ;                      
                    } 
				}     
                // printf("[%lld,%lld]:%lld\n",i,j,f[i][j]);   
			} 
		} 
        printf("%lld\n",f[m][0]);//前m-1列 顺序已确定 延伸到m+1为0 
        // puts(""); 
	}
} 
//f[i][j]=sigema(f[i][k]) 其中 k 为合法状态 

能跑对一点 但不多 然后会T 但是这不重要 因为我暂时没有预处理（