題目連結：
https://hihocoder.com/problemset/problem/1151
題目：
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描述
上一周我們研究了2xN的骨牌問題，這一周我們不妨加大一下難度，研究一下3xN的骨牌問題？
是以我們的題目是：對于3xN的棋盤，使用1x2的骨牌去覆寫一共有多少種不同的覆寫方法呢？
首先我們可以肯定，奇數長度一定是沒有辦法覆寫的；對于偶數長度，比如2，4，我們有下面幾種覆寫方式：
提示：3xN骨牌覆寫
輸入
第1行：1個整數N。表示棋盤長度。1≤N≤100,000,000
輸出
第1行：1個整數，表示覆寫方案數 MOD 12357
樣例輸入
62247088
樣例輸出
4037
題目大意：
嗯~中文題。。略過這一步0.0
題目分析：
重頭戲來啦0.0 這道題其實是個系列題，從最簡單的2*n的面積，到這道題的3*n的面積，後面還有k*n的面積的更新版。挺有意思的題目0.0
那麼，我們應該怎麼去解決這個問題呢？有兩種方法這裡會逐一去分析，第一種是矩陣快速幂，第二種代碼簡單但難想，速度也慢，就是遞推公式的方法了（其實原題自帶的題解就解釋了矩陣快速幂的方法啦）（矩陣快速幂是正解0.0）
一、矩陣快速幂（圖檔來自題目自帶的題解）
假設我們已經放好了一些骨牌，對于目前最後一列(第i列)骨牌，可能有8種情況，對于上面的這8種狀态，我們用數字來标記它們。以放置骨牌的格子為1，未放置為0，轉化為2進制數，進行狀态壓縮，可以得到以下狀态：
注意，在讨論第i行的狀态的時候，第i-1行一定是裝滿了的。
這種情況看似是從狀态1變成了狀态0，其實是不對的。它不滿足我們約定的放置方法，本質是第i行的狀态1變成了第i行的狀态7，而實際上我們應該放置的是第i+1行。
在這種規則之下，我們就可以判斷從 i 列的 某幢狀态 能否轉移為 第 i+1 列的狀态
通過枚舉8種狀态到8種狀态的轉移，我們可以得到一個8x8的矩陣M（空白的地方均為0）：
m[i][j]表示從狀态i變成狀态j的方案數。
然後我們就可以用A * M^n所求出的結果表示第n行各種狀态的方案數。（其中A應該初始化為{0, 0, 0, 0, 0, 0, 0, 1}），而對于我們尋求的答案，自然也是第n行放置為狀态7的方案數了。然後就是簡單粗暴的矩陣快速幂。
二、遞推公式法（來自聰明的CGX同學）
首先，我們先寫出如下幾種情況：
在3*2的面積中所有可能的擺放方式：
那麼，在3*n （n為偶數并且 n > 2）的面積中，除去上面3種方式的組合，擺放方式如下：
或者把最上面那一行移到上面去（這兒省略不畫）
如果除去第一種情況的互相組合，我們隻可以這樣擺放。
那麼，根據這兩種情況，我們可以得到一個遞推式：
F（n）= 3 * F（n-2）+ 2 * F（n-4）+ 2 * F（n-6）+ ... +2 * F（2）
代換變量可以得到
F（n-2）= 3 * F（n-4）+ 2 * F（n-6）+ 2 * F（n-8）+ ... + 2 * F（2）
則對一式變形可得：
F（n）= 4 * F（n-2）- F（n-2）+ 2 * F（n-4）+ 2 * F（n-6）+ ... +2 * F（2）
帶入二式得：
F（n）= 4 * F（n-2）- （3 * F（n-4）+ 2 * F（n-6）+ 2 * F（n-8）+ ... + 2 * F（2））+ 2 * F（n-4）+ 2 * F（n-6）+ ... +2 * F（2）
即：
F（n）= 4 * F（n-2）- F（n-4）
這樣這道題就解決啦0.0
題目給的10s是以不會逾時 當然啦，用矩陣快速幂優化這個遞推式，就會超級快啦0.0
代碼：（愉快的代碼時間）
矩陣快速幂：
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN=8;
const ll MOD=12357;
struct Matrix{
ll a[MAXN][MAXN];
void init(){
memset(a,0,sizeof(a));
for(int i=0;i<MAXN;i++)
a[i][i]=1;
}
};
Matrix mul(Matrix a, Matrix b)
{
Matrix ans;
for(int i=0;i<MAXN;i++)
{
for(int j=0;j<MAXN;j++)
{
ans.a[i][j]=0;
for(int k=0;k<MAXN;k++)
ans.a[i][j]=(ans.a[i][j]+(a.a[i][k]*b.a[k][j])%MOD)%MOD;
}
}
return ans;
}
Matrix qpow(Matrix a, ll n)
{
Matrix ans;
ans.init();
while(n)
{
if(n&1)
ans = mul(ans, a);
a=mul(a,a);
n>>=1;
}
return ans;
}
int main()
{
ll n;
while(scanf("%lld",&n)!=EOF)
{
Matrix a;
memset(a.a,0,sizeof(a.a));
a.a[0][7]=1;a.a[1][6]=1;a.a[2][5]=1;a.a[3][4]=1;a.a[4][3]=1;a.a[5][2]=1;a.a[6][1]=1;a.a[7][0]=1;
a.a[3][7]=1;a.a[6][7]=1;a.a[7][3]=1;a.a[7][6]=1;
Matrix ans=qpow(a,n);
printf("%lld\n",ans.a[7][7]);
}
return 0;
}
遞推：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=(int)1e8+10;
const int MOD=12357;
int main()
{
int n;
scanf("%d",&n);
if(n&1)
printf("0\n");
else if(n==0)
printf("1\n");
else if(n==2)
printf("3\n");
else
{
n/=2;
long long a=1,b=3,t;
for(int i=2;i<=n;i++)
{
t=((4*b-a)%MOD+MOD)%MOD;
a=b;b=t;
}
printf("%lld\n",t);
}
return 0;
}