对于这道题，我第一眼竟然是去看标签，然后跟着标签推思路。
题目很长，我在这就不赘述了。
简单理解，就是给定一个 n，条件是长度为n的一串 01 （我们将木属性定为 0 ，金属性定为 1） 数列中不能有连续的两个 0，因为又是环，所以当数列的首位中有一个为 0 的话，另一个就不能为 0，求满足条件的长度为 n 的数列有多少种，答案对 1000000007 取模。
说实话，我没看懂样例解释。 但并不妨碍我们去分析题目。
当 n = 1 时 只有 1 这一种情况。
当 n = 2 时 有 10 11 01 三种情况。
现在，我们以 n = 1 和 n = 2 为基础，往后进行推测。
当 n = 3 时
当首位为 0 时，只有 011 一种情况。
当首位为 1 时 有 111 101 110 三种情况。
共四种情况
当 n = 4 时
当前两位为 10 时 后面可接 10 11 两种情况。
当前两位为 11 时 后面可接 10 11 01 三种情况。
当前两位为 01 时 后面可接 11 01 两种情况。
共七种情况
同理，当 n = 5 时，对首位和倒数第二位进行分类讨论
当首位为 1 时
倒数第二位为 1 时 可接 1 0 。
倒数第二位为 0 时 可接 1 。
当首位为 0 时
倒数第二位为 1 时 可接 1 。
倒数第二位为 0 时 可接 1 。
再根据 n = 4 时的七种情况，可推出共有十一种情况。
现在我们再回头看，可以发现
n [ 3 ] = n [ 2 ] + n [ 1 ]
n [ 4 ] = n [ 3 ] + n [ 2 ]
n [ 5 ] = n [ 4 ] + n [ 3 ]
这不就是斐波那契数列嘛
既然我们已经推出了这道题的核心思想，那么剩下的就很好解决了。
但要注意 1 ≤ n ≤ 10^18 ，正常的递推肯定会超时，所以我们需要用矩阵快速幂来加速，如果还不知道的建议先去了解这道题 斐波那契数列 。
附上代码
#include<bits/stdc++.h>
#define ll long long
const int mod=1e9+7;
using namespace std;
struct miku{
ll a[3][3];
miku()
{
memset(a,0,sizeof(a));
}
}MIKU,IA;//矩阵
miku operator *(const miku &x,const miku &y)//重载运算符
{
miku z;
for(int k=1;k<=2;k++)
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
return z;
}
void Vocaloid()
{
MIKU.a[1][1]=3,MIKU.a[1][2]=1;
MIKU.a[2][1]=0,MIKU.a[2][2]=0;
IA.a[1][1]=1,IA.a[1][2]=1,IA.a[2][1]=1,IA.a[2][2]=0;
}//初始矩阵的赋值
ll read()//快读
{
long long x=0,flag=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') flag=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*flag;
}
int T;
ll n;
int main()
{
scanf("%d",&T);
while(T--)
{
n=read();
Vocaloid();
miku ans=MIKU;
if(n<=2)//特判一下，当 n ≤ 2 时，直接输出
{
if(n==1) puts("1");
else if(n==2) puts("3");
continue ;
}
n-=2;
do
{
if(n&1) ans=ans*IA;
IA=IA*IA;
n>>=1;
}while(n);
printf("%d
",ans.a[1][1]%mod);
}
return 0;
}
PS：
其实此题和这道题和像 单词 。
如果有什么问题可以在评论区提出，我会尽己所能去回答的 （毕竟我也才学信息没多久） 。
这是本人的第一篇题解，如果有什么问题还请管理员大大提出，我会加以改正 QAQ 。