蓝桥杯ACwing习题

题目 ：https://www.acwing.com/problem/content/4409/

解析 ：根据题目我们可以知道 问的是方案数 那么首先就想到了 dp 仔细想一下 发现类似于蒙德里安的梦想那道状态压缩的题 ， 所以我们先考虑怎么定义 f[i][j] 
f[i][j] 表示的是 已经放了前 i 行 且第 i + 1 填满了  j 个格子 , 由此我们画图可以知道

f[i][0] = f[i - 1][2 ] + f[i - 1][0]
f[i][1] = f[i - 1][1]  + f[i - 1][0] * 2;
f[i][2] =  f[i - 1][0] +f[i - 1][1];

矩阵用于解决大数据问题

设Fi = { fi0 , fi1 , fi2};
Fi -1= { fi - 10 , fi - 11 , fi - 12}:
Fi- 1 * A  = Fi
由上面的可以得到 
A = 1 2 1
        0 1 1
        1 0  0
代码
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e7 + 10 , mod = 1e9 + 7;
typedef long long LL;

int dp[N][3]; // 已经放好了前 i 列 , 且第 i + 1 列放了 0 1 2 个的方案数 

void mul(LL f[] , LL a[] , LL b[][3])
{
       LL temp[3] = {0};
    
    for(int i = 0 ; i < 3 ; i ++)
      for(int j = 0 ; j < 3 ; j ++)
          temp[i] = (temp[i] + a[j] * b[j][i]) % mod;
          
    memcpy(f , temp ,sizeof temp);
}

void mul(LL a[3][3] , LL b[3][3] , LL c[3][3])
{
    LL temp[3][3] = {0};
    
    for (int i = 0; i < 3 ; i ++)
       for (int j = 0; j < 3 ; j ++)
         for (int k = 0; k < 3 ; k ++)
            temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % mod;
    
    memcpy(a , temp , sizeof temp);
}

int main()
{
    int n;
    cin >> n;
    
    // 求 dp[n][0] ?
    n --;
    LL a[][3] =  {{ 1, 2, 1 },
                  { 0 ,1 ,1 },
                  { 1,0 ,0 }};
                
    LL f[] = {1 , 2 , 1};
    
    while (n)
    {
        if(n & 1) mul(f , f , a);
          n >>= 1;
        mul(a , a , a);
      
    }
    
    cout << f[0] << endl;
    
    return 0;
}