题目传送门
【题目大意】
往一个$N*M$的矩阵中放$1*2$的小长方形，可以横着放也可以竖着放，不能重叠，求把大矩阵填满有多少种方案。
【思路分析】
我们对每一行单独分析，对于第$i$行中的第$j$格，可能有一下三种状态：
1.是一个横着放的小长方形的其中一格
2.是竖着放的小长方形的下面一格
3.是竖着放的小长方形的上面一格
对于第1、2种状态可以直接处理，而第3种状态会对下面一行形成影响，即第$i+1$行第$j$格不能放小长方形，这种状态要单独考虑。
我们选择用一个$M$位的二进制数来记录每一行的状态，其中如果第$j$位为1，则表示这是上面的第3种状态；如果为0，则是1、2种状态。
设$f[i][j]$表示第$i$行状态为$j$时，前$i$行的总方案数。
第$i-1$行的状态$k$能转移到第$i$行的状态$j$，当且仅当：
1.$j$和$k$执行按位与运算的结果为0，这保证了$k$中每个数字1下方为0，即第2种状态。
2.$j$和$k$执行按位或运算的结果的二进制表示中，每一段连续的0都必须是偶数个，这些0代表的是若干个横着的小长方形。
我们预处理出$[0,2^M-1]$内所有满足“二进制表示下每一段连续的0都有偶数个”的整数，记录在集合$S$中，则
$$f[i][j]=\sum_{j\&k=0且j|k \in S}f[i-1][k]$$
初始值：$f[0][0]=1$，其余均为0
目标：$f[N][0]$
时间复杂度：$O(4^MN)$
【代码实现】
1 #include<iostream> 2 #include<cstring> 3 #define ll long long 4 #define rg register 5 #define go(i,a,b) for(rg int i=a;i<=b;i++) 6 using namespace std; 7 int n,m; 8 ll f[12][1<<11]; 9 bool ready[1<<11]; 10 int main(){ 11 while(cin>>n>>m&&n){ 12 go(i,0,(1<<m)-1){//预处理 13 bool t=0,k=0; 14 go(j,0,m-1) 15 if(i>>j&1) k|=t,t=0; 16 else t^=1; 17 ready[i]=k|t?0:1; 18 } 19 f[0][0]=1; 20 go(i,1,n) go(j,0,(1<<m)-1){ 21 f[i][j]=0; 22 go(k,0,(1<<m)-1) 23 if((j&k)==0&&ready[j|k]) f[i][j]+=f[i-1][k]; 24 } 25 cout<<f[n][0]<<endl; 26 } 27 return 0; 28 } 代码戳这里
转载于:https://www.cnblogs.com/THWZF/p/11226784.html
