题解 P1962 【斐波那契数列】
斐波那契数列？直接f[i]=f[i-1]+f[i-2]不就行了吗？怎么提高+的难度？（其实真没有这么难）突然发现n在long long范围内...这...连线性都不行？嗯......怪不得要用矩阵的，那接下来我就来说说如何用矩阵解决这题：
首先，做这题要懂矩阵乘法：我们假设有一个n*m的矩阵A和一个m*p的矩阵B，那么它们相乘可以得到一个n*p的矩阵C，则C[i][j]等于矩阵A的第i行与矩阵B的第j行的乘积和，即 。那么这样的矩阵乘法有什么意义呢？
对于这个问题，我们考虑以下的线性方程组：
现在我们将a作为矩阵A的元素，b作为矩阵B的元素，c作为矩阵C的元素。根据矩阵乘法，那么就有以下关系：
这样以上方程组就可以简写为AB = C。我们仔细分析这个式子，可以发现矩阵A相当于一种变换方式，它把列向量B变为了列向量C。同理，对于这题，我们是否可以考虑构造一个矩阵A，将当前的状态乘以它来得到下一个状态？答案是可以的。
既然这样，我们现在考虑构造矩阵（比矩阵加速模板的矩阵好构建多了）。对于递推关系式f[i]=f[i-1]+f[i-2]，我们发现影响f[i]最早的状态是f[i-2]，相当于我们用f[i-2]更新过f[i]后，这个状态就可以不要了，但f[i-1]还得留着，因为他还要去更新f[i+1]，所以我们构造的矩阵应该是2*2的。 构造好的矩阵先放这，我下面详细解释：
好，现在我们再建立一个列向量B（数组存储），存储在当前状态下我们仍然需要的两个斐波那契数列里的数值（f2是f1的下一个）：
现在我们再来一次矩阵乘法，得到以下两个式子：
关系已经很明显了，根据斐波那契数列，第一个式子的值就等于f2的下一个斐波那契值f3，而原来f1位置上的值也更新成了f2（因为f1已经不需要再用到了）
总结一下，有了这个我们构造好的矩阵，我们每乘一次，就会得到斐波那契数列的下一项。也许你会问：用矩阵乘法的效率还不如直接递推呢！表面上是这样，但不要忘了，还有矩阵快速幂哦。如果我们想得到斐波那契的第n（除开头的1、1）项，那么我们就可以用列向量B的初值（即1、1）乘以n个构造矩阵。由于矩阵乘法满足结合律，我们可以先将n个构造矩阵乘起来（这里就可以套用矩阵快速幂的模板啦），然后将所得到的矩阵再乘以列向量B，就可以得到斐波那契数列的第n项啦。
那个......矩阵快速幂我在这就不讲了......可以去参考一些资料，其实跟普通的快速幂没差多少......
代码如下：
#include<cstdio>
#include<cstring>
using namespace std;
long long n,a[3],mul[3][3],res[3][3],tmp[3][3],tp[3];
void mul_1()
{
memset(tmp,0,sizeof(tmp));
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
for(register int k=1;k<=2;k+=1)
tmp[i][j]=(tmp[i][j]+res[i][k]*mul[k][j])%1000000007;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
res[i][j]=tmp[i][j];
}
void mul_2()
{
memset(tmp,0,sizeof(tmp));
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
for(register int k=1;k<=2;k+=1)
tmp[i][j]=(tmp[i][j]+mul[i][k]*mul[k][j])%1000000007;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
mul[i][j]=tmp[i][j];
}
void solve()
{
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
tp[i]=(tp[i]+res[i][j]*a[j])%1000000007;
printf("%lld\n",tp[1]);
}
int main()
{
scanf("%lld",&n);
if(n<=2)printf("1\n");
else
{
a[1]=a[2]=1;
for(register int i=1;i<=2;i+=1)
res[i][i]=1;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
mul[i][j]=1;
mul[2][2]=0;
n-=2;
while(n)
{
if(n&1)mul_1();
n>>=1;
mul_2();
}
solve();
}
return 0;
}