蒟蒻在做P3390矩阵快速幂这道题时，发现自己写的程序必须使矩阵

[1,1]

[1,0]

的$n-1$次方与矩阵

[1,1]

相乘，才能得出正确的答案，但题解区的大佬都说应该是$n-2$次方，我也是这样认为的，但我的程序一定要$n-1$次方，虽然AC了这道题，但蒟蒻本着严谨的态度还是求大佬们解释一下为什么会这样吧。

100分记录

20分记录

AC代码：

#include<bits/stdc++.h>
using namespace std;
long long inf=1000000007,n;
struct node
{
	long long a[3][3];
}A,F;
node cheng(node a,node b)
{
	node c;
	for(int i=1;i<=2;i++)
	for(int j=1;j<=2;j++)
		c.a[i][j]=0;
	for(int i=1;i<=2;i++)
	for(int j=1;j<=2;j++)
	for(int k=1;k<=2;k++)
	{
		c.a[i][j]+=a.a[i][k]%inf*b.a[k][j]%inf;
		c.a[i][j]%=inf;
	}
	return c;
}
node p(long long x)
{
	if(x==1) return A;
	node res=p(x/2);
	if(x%2==0) return cheng(res,res);
	return cheng(cheng(res,res),A);
}
int main()
{
	cin>>n;
	if(n==1||n==2)
	{
		cout<<1<<endl;
		return 0;
	}
	A.a[1][1]=1;A.a[1][2]=1;
	A.a[2][1]=1;A.a[2][2]=0;
	F.a[1][1]=F.a[1][2]=1;
	node q=p(n-1);
	node r;
	r.a[1][1]=r.a[1][2]=0;
	for(int i=1;i<=1;i++)
	for(int j=1;j<=2;j++)
	for(int k=1;k<=2;k++)
	{
		r.a[i][j]+=q.a[i][k]%inf*F.a[k][j]%inf;
		r.a[i][j]%=inf;
	}
	cout<<r.a[1][1]<<endl;
	return 0;
}