题解 P1962 【斐波那契数列】
ouuan
2018-07-11 23:07:30
看楼上dalao们都是用f[n],f[n+1]推f[n+1],f[n+2]然而我是用f[n],f[n+1]推f[n+2],f[n+3]
（然而只是预处理了矩阵的二次方）
f[n+2]=f[n]+f[n+1]不用多说
f[n+3]=f[n+1]+f[n+2]=f[n]+2*f[n+1]
因此用来计算的矩阵就是
| 1 | 1 |
| :----------: | :----------: |
| 1 | 2 |
这样算的话貌似能快一个可以忽略不计的常数..
嗯，我这篇题解就是从[P1939](https://www.luogu.org/blog/yyfouuan/solution-p1939)那抄过来的..因为我两题都是这样没有重复推的。
代码如下：
```
#include <iostream>
using namespace std;
const long long M=1000000007;
struct matrix
{
long long a[2][2]={{0,0},{0,0}};
matrix operator*(const matrix& b) const
{
matrix out;
long long i,j,k;
for (i=0;i<2;++i)
{
for (j=0;j<2;++j)
{
for (k=0;k<2;++k)
{
out.a[i][j]=(out.a[i][j]+this->a[i][k]*b.a[k][j])%M;
}
}
}
return out;
}
};
int main()
{
long long n,i;
matrix f,ans;
f.a[0][0]=f.a[0][1]=f.a[1][0]=1; //初始化为上文所述的矩阵
f.a[1][1]=2;
ans.a[0][0]=ans.a[1][1]=1; //初始化为对角线为1的矩阵，即单位矩阵
cin>>n;
for (i=62;i>=0;--i) //二进制版快速幂，个人比较喜欢，平常用递归的小伙伴们也可以学一学
{
ans=ans*ans;
if ((1ll<<i)&((n-1)>>1)) //注意计算的是矩阵的(n-1)/2次方
{
ans=ans*f;
}
}
if (n&1) ////输出的时候判断一下n处于向量中的哪个位置，即n%2是几
}
{
cout<<(ans.a[0][0]+ans.a[0][1])%M;
}
else
{
cout<<(ans.a[1][0]+ans.a[1][1])%M;
}
return 0;
}
```