lanqiao OJ 246 矩阵计数

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ; 
const int N = 6 ; 
int row[1<<N] ;//记录行的合法排列，（记得数组开大！！！） 
int n , m ;
int f[N][1<<N][1<<N] ;//当前第i行的状态为row[j]并且第i-1行状态为row[k]的方案数 
 
bool check(int x){//判断行合法性 
  int num = 0 ;
  while(x > 0){
    if((x&1) == 1) num ++ ;
    else num = 0 ;
    if(num >= 3) return true ;
    x >>= 1 ;
  }
  return false ;
}
 
int main(){
  cin >> n >> m ;
  memset(row,0,sizeof(row)) ;
  int t = 0 ;
  for(int i = 0 ; i < (1 << m) ; i++){//记录行合法性 
    if(!check(i)){
      row[t] = i ;
      t ++ ;
    }
  }
  memset(f,0,sizeof(f)) ;
  for(int i = 0 ; i< t ; i++) f[0][row[i]][0] = 1 ;//第一行初始化，第一行的没有前一行，所以我们把前一行看作是0状态，因为他不会和任何一个冲突 
  
  for(int i = 1 ; i < n ;i ++){//遍历每一行 
    for(int j = 0; j < t ; j ++){//遍历每一行的状态 
      for(int k = 0 ; k < t ; k ++){//遍历上一行的状态 
        for(int p = 0 ; p < t ; p ++){//遍历上一行的上一行的状态 
          if(((row[j] & row[k]) & row[p]) == 0){//这三行不能连续三个1 
            f[i][row[j]][row[k]] += f[i-1][row[k]][row[p]] ;
          }
        }
      }
    }
  }
  long long ans = 0 ;//最后一行的所有组合和就是答案 
  for(int i = 0 ; i < t ; i ++){
    for(int j = 0 ; j < t ; j ++){
      ans += f[n-1][row[i]][row[j]] ;
    }
  }
  cout << ans << endl ;
}