由于棋盘只有两行，所以如果第i列的骨牌竖着放，那么就转移为第1列到第i-1列骨牌有多少种摆法
如果第一行第i列骨牌横着放，那么第二行第i列也要横着放，那么就转移为了第1列到第i-2列骨牌有多少种方法
dp[i] = dp[i-1] + dp[i-2],但是列数太多了。 这种递推的算式可以用矩阵快速幂来优化
所以时间复杂度瞬间变为O(logn)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
LL ans;
const int MOD = ;
//矩阵快速幂 a[i] = a[i-1] + a[i-2] struct Matrix
{
LL m[][];
};
Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
Matrix ret;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
ret.m[i][j] = ;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
for(int k=; k<; ++k)
if(lhs.m[i][k]!= && rhs.m[k][j]!=)
ret.m[i][j] = (ret.m[i][j] + lhs.m[i][k] * rhs.m[k][j])%MOD; return ret;
}
Matrix operator^(Matrix a, int k)
{
Matrix ret;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
ret.m[i][j] = ;
ret.m[][] = ;
while(k)
{
if(k&)
ret = ret * a;
k>>=;
a = a * a;
}
return ret;
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
Matrix tmp;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
tmp.m[i][j] = ;
tmp.m[][] = ;
Matrix final = tmp ^ (n-);
LL ans = ( * final.m[][] + * final.m[][])%MOD;
printf("%lld\n",ans);
}
return ;
}