lanqiaoOJ 2110 积木画

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
typedef long long LL ;
const int N = 10000010 ,M = 1e9 + 7 ;
LL dp[N][4] ;//\/\表示第i-1列已经操作完成且第i列的状态为j的所以方案的数量
int d[4][4] ={//\\表示i-1状态为j时能否使第i列状态变成k状态
  {1,1,1,1},
  {0,0,1,1},
  {0,1,0,1},
  {1,0,0,0}
};
int main(){
  int n ; cin>> n ;
  dp[1][0] = 1 ;
  for(int i =2 ; i <= n+1 ; i ++){//\\对列进行遍历
    for(int j= 0 ; j < 4 ;  j ++){//\\对前面一列的四种状态进行遍历
      for(int k = 0 ; k < 4 ; k ++){//\\对当前一列四种状态进行遍历
        dp[i][k] = (dp[i][k] + dp[i-1][j] * d[j][k] ) % M;
               // \\当前这一列的k状态可以由上一列的j状态变化而来
      }
    }
  }
  cout << dp[n+1][0] << endl ;
  return 0 ;
  
}