题目
【题目描述】
ITX351 要铺一条 $2 imes N$ 的路，为此他购买了 $N$ 块 $2 imes 1$ 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 $1 imes 1$ 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 $1 imes 1$ 的砖块分开铺，**不让两块砖有相邻的边**，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！
也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
【输入格式】
每个测试点包含多组数据，输入文件的第一行是一个正整数 $T$，表示数据的组数。注意各组数据之间是独立无关的。
接下来 $T$ 行，每行包含一个正整数 $N$，代表一组数据中路的长度。
【输出格式】
输出应包含 $T$ 行，对于每组数据，输出一个正整数，表示满足条件的方案数。
由于答案可能非常的大，你只需要输出答案对 $1000000007 (10^9 + 7)$ 取模后的结果。
【样例输入】
3
1
2
4
【样例输出】
0
0
6
【数据范围与提示】
所有测试数据的范围和特点如下表所示：
|测试点编号|$N$ 的规模|$T$ 的规模|
|:-:|:-:|:-:|
|$1$|$N le 10$|$T le 10$|
|$2$|$N le 10$|$T le 10$|
|$3$|$N le 10^5$|$T le 50$|
|$4$|$N le 10^5$|$T le 50$|
|$5$|$N le 10^5$|$T le 50$|
|$6$|$N le 2 imes 10^9$|$T le 50$|
|$7$|$N le 2 imes 10^9$|$T le 50$|
|$8$|$N le 2 imes 10^9$|$T le 50$|
|$9$|$N le 2 imes 10^9$|$T le 500$|
|$10$|$N le 2 imes 10^9$|$T le 500$|
题解
可以发现，在两个 $ 1 imes 1 $ 的方砖中放的方案数是唯一的（因为上下交错），而且只要两个方砖间的距离 $ geq 3 $ 就一定可以填（具体参照样例）
那么只要考虑左边和右边的方案数的乘积
对于一段空格，要么就是一个 $ 2 imes 1 $ 的方砖，要么就是 $ 1 imes 2 $ 的两个一起填
记 $ f[i] $ 表示前 $ i $ 个格的方案数，则有 $ f[i]=f[i-1]+f[i-2] $，这很斐波那契
那么 $ ans=sum_{i-0}^{n-3}sum_{j=0}^{n-i-3}f[i] imes f[j] $
这很卷积，但上 FFT 要 $ O(nlog n) $，显然过不去
斐波那契数列有一个性质 $ f[n+2]+1=sum_{i=0}^{n}f[i] $
那么 $ ans=sum_{i=0}^{n-3}f[i] imes (f[n-i-1]-1) $，$ 2 imes 10^9 $ 依然过不去
（然后测试时我就不会了）
开始推式子
$ ans=sum_{i=0}^{n-3}f[i] imes (f[n-i-1]-1) $
$ =1-f[n-1]+sum_{i=0}^{n-3}f[i] imes f[n-i-1] $
记 $ s[n]=sum_{i=0}^{n}f[i] imes f[n-i] $
$ = f[n]+f[n-1]+sum_{i=0}^{n-2}f[i] imes f[n-i]$
$ =f[n]+f[n-1]+sum_{i=0}^{n-2}f[i] imes (f[n-i-1]+f[n-i-2]) $
$ =f[n]+f[n-1]+sum_{i=0}^{n-2}f[i] imes f[n-i-1]+sum_{i=0}^{n-2}f[i] imes f[n-i-2] $
$ =f[n]+sum_{i=0}^{n-1}f[i] imes f[n-i-1]+sum_{i=0}^{n-2}f[i] imes f[n-i-2] $
$ =f[n]+s[n-1]+s[n-2] $
然后发现可以矩阵优化
$ left{ egin{matrix} f[n-1]\f[n-2]\s[n-1]\s[n-2] end{matrix} ight} left{ egin{matrix} 1 1 0 0 \1 0 0 0\1 1 1 1 \0 0 1 0 end{matrix} ight}=left{ egin{matrix} f[n]\f[n-1]\s[n]\s[n-1] end{matrix} ight} $
则 $ ans=1-f[n-1]+s[n-1]-f[n-2] imes f[1]-f[n-1] imes f[0] $
$ = 1+s[n-1]-2 imes f[n-1]-f[n-2]$
然后就可以了（预处理矩阵会更快）
时间效率 $ O(Tlog n imes 4^3) $
代码
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define _(d) while(d(isdigit(ch=getchar()))) 4 using namespace std; 5 int R(){ 6 int x;bool f=1;char ch;_(!)if(ch=='-')f=0;x=ch^48; 7 _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;} 8 const int N=1e5+6,P=1e9+7; 9 int n; 10 struct Matrix{ 11 LL s[10][10]; 12 Matrix(){memset(s,0,sizeof s);} 13 void one(){ 14 s[1][1]=s[1][2]=s[2][1]=s[3][1]=s[3][2]=s[3][3]=s[3][4]=s[4][3]=1; 15 return; 16 } 17 void S(){s[1][1]=s[2][1]=s[4][1]=1,s[3][1]=2;return;} 18 Matrix friend operator *(Matrix a,Matrix b){ 19 Matrix c; 20 for(int i=1;i<=5;i++) 21 for(int j=1;j<=5;j++) 22 for(int k=1;k<=5;k++) 23 c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%P; 24 return c; 25 } 26 }; 27 int power(){ 28 n=R()-3; 29 if(n<1)return n==0?1:0; 30 Matrix a,b,res; 31 a.one(),b.S(),res.one(); 32 for(;n;n>>=1,a=a*a) 33 if(n&1)res=res*a; 34 b=res*b; 35 return ((1+b.s[3][1]-b.s[2][1]-2*b.s[1][1])%P+P)%P; 36 } 37 int main(){ 38 for(int T=R();T--;)printf("%lld ",power()*2ll%P); 39 return 0; 40 }