題目大意：有兩種積木塊，I型和L型，給定一段2*N的畫布，問擺滿總共有多少種方式？

解法：狀態壓縮dp（強烈建議拿個筆跟著畫一下狀態，慢慢就懂了）

首先我們規定一下此題解中提到的狀態：
在第i列中會有兩格（因為2*N），0表示未被占，1表示被占了，即如果兩個格子都未被占則表示00，上面的未被占，下面的被占了表示01；同理10表示上面被占，下面未被占，11表示全都被占

另外，一旦發生狀態轉移，那么一定會讓當前的列被占滿！（為了防止重復情況，所以需要規定當前列占滿，也可以規定下一列占滿），這里看不懂先跳過，后面就看懂了

解題思路：
1.定義狀態數組f[i][j]：i表示當前的位置，j表示當前位置的狀態，f[i][j]表示在前i-1已經擺滿的前提下總共有多少中擺放方式

2.構建轉移數組g[j][k]：j表示轉移前的狀態，也就是當前（第i列）狀態；k表示轉移后i+1列的狀態
（1）對于轉移前第i列會有四種狀態即00，01，10，11（再次強調i-1列已經滿了，第i列可能被占是因為放i-1列的時候“不小心”占用了它，這也是為什么上面要規定發生狀態轉移，當前列被占滿）
（2）前提：一旦發生狀態轉移就要填滿第i列！那么如果當前列為00，我們便有四種擺放方式把它填滿，自己動手畫一下，加深理解！四種方式擺放完對應的i+1列也會有四種狀態，所以第i列擺放為00的時候，可以讓i+1出現00，01，10，11四種情況！后面的用下面的二維表格表示

	00	01	10	11
00	1	1	1	1
01	0	0	1	1
10	0	1	0	1
11	1	0	0	0

由此也可得我們的轉移數組g[4][4],而00，01，10，11在二進制轉十進制中剛好對應0123

3.狀態轉移公式：f[i+1][k]+=f[i][j]*g[j][k]，首先理清這里面的i，j，k都是什么。f[i+1][k]就已經是下一個狀態了，即第i列擺滿，且i+1列的狀態為k。而后面的f[i][j]*g[j][k],即f[i][j]想變成f[i+1][k]，就必須滿足g[][]!=0才行，因為g[][]=1才表示可以轉移到f[i+1][k]狀態啊！

4.關于狀態數組的初始化，f[1][0]=1，我們一開始放的時候其實就相當于第0列以及被鋪滿，且第1列一個沒放；初始化為1，這個地方我是通過自己推到前幾項得來的！

5.循環：首先是列數的循環，第i列的時候，我們得到的是i+1，而初始化為1，所以我們遍歷為1~n；其次就是每一列可能出現的四種狀態j和四種擺放方式k的循環

下面的代碼里面也有解釋，如果還不懂就結合代碼來看或許會簡單不少QWQ

#include<bits/stdc++.h>
using namespace std;
using ll=long long;const int N = 1e7+5;
const int MOD = 1e9+7;int n;
int g[4][4]={{1,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,0},
};//g[當前狀態][轉移狀態]
//轉移狀態：在i放滿的前提下i+1的狀態int f[N][4];//狀態轉移數組
//f[i][j]表示前i-1已經放滿，j表示第i列狀態，00，01，10，11分別對應0，1，2，3
//f[i][j]的值就是到此時的個數              int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;f[1][0]=1;//初始化初始狀態，下一個狀態是對第一列進行擺放，相當于第0列全部占滿了for(int i=1;i<=n;i++)//1~n的狀態對應初始狀態~最終的前一個狀態{for(int j=0;j<4;j++)//遍歷四種第i列的四種狀態，即00，01，10，11{for(int k=0;k<4;k++)//遍歷狀態轉移{f[i+1][k]=(f[i+1][k]+f[i][j]*g[j][k])%MOD;}}}cout<<f[n+1][0];//n列放滿，且n+1列當前狀態為00，即什么也不放return 0;
}

另外還是有些優化的
1.滾動數組優化：我寫到下面的代碼里面吧，這樣更直觀！
2.乘法相比于加減更耗時間，我們可以在進行狀態轉移的時候，可以先判斷g[][]是否為1，詳見代碼吧！
?

#include<bits/stdc++.h>
using namespace std;
using ll=long long;const int N = 1e7+5;
const int MOD = 1e9+7;int n;
int g[4][4]={{1,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,0},
};
//優化為滾動數組
//1.將初始的f[N][4]改為f[2][4]
//2.將所有的f[這個位置&1][]即可
//3，記得每一輪狀態轉移開始前，將下一個狀態對應的數組元素初始化為0
int f[2][4];             int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;f[1][0]=1;for(int i=1;i<=n;i++){memset(f[i+1&1],0,sizeof f[0]);// 將下一個狀態對應的數組元素初始化為 0// (i + 1) & 1 確定要操作的是 f[0] 還是 f[1]// sizeof f[0] 表示要初始化的字節數for(int j=0;j<4;j++){for(int k=0;k<4;k++){if(g[j][k])//判斷是否為1，為1進行下面的狀態轉移f[i+1&1][k]=(f[i+1&1][k]+f[i&1][j])%MOD;}}}cout<<f[n+1&1][0];return 0;
}