题目链接
https://www.luogu.com.cn/problem/P5303
题解
神仙推式子题。
容易发现整个区域可以分为三部分：第一个 \(1 \times 1\) 方块左边，两个 \(1 \times 1\) 方块中间部分（至少 \(2 \times 3\) 的区域），第二个 \(1 \times 1\) 方块右边部分。
如下图所示：
其中两个 \(1 \times 1\) 方块是同行还是异行取决于中间列数的奇偶性（奇数为异行，偶数为同行）。
如果两个 \(1 \times 1\) 方块的位置定下来了，上图中间的红色区域就只有一种摆法。
而左边黑色区域和右边绿色区域，显然分别有 \(F_x,F_y\) 种摆法（\(F_x\) 为斐波那契数列，满足 \(F_0=F_1=1\)，\(F_i=F_{i-1}+F_{i-2}\)）。
根据乘法原理，答案可以表示为：
$$2 \sum_{x=0}^{n-3} \sum_{y=0}^{n-x-3}F_x \times F_y$$
（中间的红色区域考虑上下行交换，所以答案乘二）
运用乘法分配律：
$$2 \sum_{x=0}^{n-3}F_x \sum_{y=0}^{n-x-3}F_y$$
斐波那契数列满足 \(\sum_{i=0}^x F_i=F_{x+2}-1\)，所以把后面的 \(\sum F_y\) 换掉：
$$2 \sum_{x=0}^{n-3}F_x \times (F_{n-x-1}-1)$$
整理后得到：
$$2 (\sum_{x=0}^{n-3}F_x \times F_{n-x-1}-F_{n-1}+1)$$
现在重点放到 \(\sum_{x=0}^{n-3}F_x \times F_{n-x-1}\) 上。
我们设：
$$G_n=\sum_{x=0}^{n}F_x \times F_{n-x}$$
将 \(x=n\) 和 \(x=n-1\) 提出来：
$$G_n=\sum_{x=0}^{n-2}F_x \times F_{n-x} + F_n+F_{n-1}$$
把 \(F_{n-x}\) 也拆开：
$$G_n=\sum_{x=0}^{n-2}F_x \times (F_{n-x-1}+F_{n-x-2})+F_n+F_{n-1}$$
用乘法分配律：
$$G_n=\sum_{x=0}^{n-2}F_x \times F_{n-x-1}+\sum_{x=0}^{n-2}F_x \times F_{n-x-2}+F_n+F_{n-1}$$
把 \(F_{n-1}\) 放回到式子的第一块：
$$G_n=\sum_{x=0}^{n-1}F_x \times F_{n-x-1}+\sum_{x=0}^{n-2}F_x \times F_{n-x-2}+F_n$$
到这里终于豁然开朗啦。
$$G_n=G_{n-1}+G_{n-2}+F_n$$
把 \(G_n\) 代入到答案中，可得答案为：
$$2(1+G_{n-1}-2 \times F_{n-1}-F_{n-2})$$
最后的问题就是用矩阵快速幂来递推 \(F_n,G_n\) 了。
稍微推一下就能得到：
$$\begin{bmatrix} F_{n-1} & F_{n-2} & F_{n-3} & G_{n-1} & G_{n-2} & G_{n-3} \end{bmatrix} \\ \times \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \\ = \begin{bmatrix} F_n & F_{n-1} & F_{n-2} & G_n & G_{n-1} & G_{n-2} \end{bmatrix}$$
时间复杂度 \(O(6^3 T\log n)\)。
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct mat
{
long long a[15][15];
mat(int x=0)
{
memset(a,0,sizeof(a));
for(int i=1;i<=6;i++)
a[i][i]=x;
}
mat operator*(const mat&A)const
{
mat ans;
for(int k=1;k<=6;k++)
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*A.a[k][j])%MOD;
return ans;
}
}f,g;
void init()
{
//[f_3,f_2,f_1,g_3,g_2,g_1]
f.a[1][1]=3,f.a[1][2]=2,f.a[1][3]=1,f.a[1][4]=10,f.a[1][5]=5,f.a[1][6]=2;
/*
1 1 0 1 0 0
1 0 1 1 0 0
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 1 0 1
0 0 0 0 0 0
*/
g.a[1][1]=1,g.a[1][2]=1,g.a[1][3]=0,g.a[1][4]=1,g.a[1][5]=0,g.a[1][6]=0;
g.a[2][1]=1,g.a[2][2]=0,g.a[2][3]=1,g.a[2][4]=1,g.a[2][5]=0,g.a[2][6]=0;
g.a[3][1]=0,g.a[3][2]=0,g.a[3][3]=0,g.a[3][4]=0,g.a[3][5]=0,g.a[3][6]=0;
g.a[4][1]=0,g.a[4][2]=0,g.a[4][3]=0,g.a[4][4]=1,g.a[4][5]=1,g.a[4][6]=0;
g.a[5][1]=0,g.a[5][2]=0,g.a[5][3]=0,g.a[5][4]=1,g.a[5][5]=0,g.a[5][6]=1;
g.a[6][1]=0,g.a[6][2]=0,g.a[6][3]=0,g.a[6][4]=0,g.a[6][5]=0,g.a[6][6]=0;
}
mat fpow(mat x,int y)
{
mat ans(1);
while(y)
{
if(y&1)ans=ans*x;
x=x*x;
y>>=1;
}
return ans;
}
int main()
{
int t;
cin>>t;
init();
while(t--)
{
int n;
cin>>n;
if(n<=2)cout<<0<<endl;
else
{
mat res=f*fpow(g,n-3);
cout<<(2*(-2*res.a[1][2]-res.a[1][3]+res.a[1][5]+1)%MOD+MOD)%MOD<<endl;
}
}
return 0;
}