题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列：
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入输出格式
输入格式：
·第 1 行：一个整数 n
输出格式：
第 1 行： f(n) mod 1000000007 的值
输入输出样例
输入样例#1：
5
输出样例#1：
5
输入样例#2：
10
输出样例#2：
55
说明
对于 60% 的数据： n ≤ 92
对于 100% 的数据： n在long long(INT64)范围内。
在这道题中，我们可以仔细的介绍一下矩阵乘法：
一个m行n列的矩阵与一个n行p列的矩阵可以相乘，得到的结果是一个m行p列的矩阵，
其中的第i行第j列位置上的数为第一个矩阵第i行上的n个数与第二个矩阵第j列上的n个数对应相乘后所得的n个乘积之和。
矩阵乘法满足结合律，但不满足交换律和约去律
矩阵加法就是相同位置的数字加一下。
矩阵减法也类似。
矩阵乘以一个常数，就是所有位置都乘以这个数。
但是，等到矩阵乘以矩阵的时候，一切就不一样了。
这要怎么理解呢
矩阵的本质就是线性方程式，两者是一一对应关系。如果从线性方程式的角度，理解矩阵乘法就毫无难度。
下面是一组线性方程式。
矩阵的最初目的，只是为线性方程组提供一个简写形式。
老实说，从上面这种写法，已经能看出矩阵乘法的规则了：系数矩阵第一行的2和1，各自与 x 和 y 的乘积之和，等于3。不过，这不算严格的证明，只是线性方程式转为矩阵的书写规则。
下面才是严格的证明。有三组未知数 x、y 和 t，其中 x 和 y 的关系如下。
x 和 t 的关系如下。
有了这两组方程式，就可以求 y 和 t 的关系。从矩阵来看，很显然，只要把第二个矩阵代入第一个矩阵即可。
从方程式来看，也可以把第二个方程组代入第一个方程组。
上面的方程组可以整理成下面的形式。
最后那个矩阵等式，与前面的矩阵等式一对照，就会得到下面的关系。
矩阵乘法的计算规则，从而得到证明。
好，那我们再看这道题
矩阵如下：
那就会问了：是怎么求出来的呢？
这下就明白了吧~
所以我们需要计算的就是：
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
const LL mod=1000000007;
const int N=10;
int n;
struct node{
int m[N][N];
node operator * (const node &a) const{
node c={}; //需要另用一个矩阵计算乘法的结果
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+(LL)m[i][k]*a.m[k][j])%mod;
return c;
}
void clear()
{
memset(m,0,sizeof(m));
}
node KSM(LL p) //快速幂模板
{
node an=(* this),a=(*this);
// an.clear();
// for (int i=1;i<=n;i++)
// an.m[i][i]=1;
while (p)
{
if (p&1)
an=an*a;
a=a*a;
p>>=1;
}
return an;
}
};
main()
{
LL p;
scanf("%lld",&p);
node m,ans;
m.m[1][1]=1; m.m[1][2]=1;
m.m[2][1]=1; m.m[2][2]=0;
n=2;
ans=m.KSM(p-1);
printf("%d
",(ans.m[2][1])%mod);
}