M斐波那契数列
此题对数学基础要求较高
来源矩阵乘法_百度百科
一个m*n的矩阵是一个由m行n列元素排成的矩形阵列。矩阵里的元素可以是数字符号或者数学式.
形如[acbd][abcd]的数表称为二阶矩阵，其中a,b,c,d称为这个矩阵的元素。
形如 [x1x2][x1x2] 的有序对称为列向量
设
A=[acbd]A=[abcd] B=[x1x2]B=[x1x2]
则C=[ax1+bx2ax2+bx1]C=[ax1+bx2ax2+bx1]
称为二阶矩阵A与平面向量B的乘积，记为AB=C
更一般的矩阵乘法如下
设A为m×pm×p的矩阵，B为p×np×n 的矩阵，那么称m×nm×n的矩阵C为矩阵A与B的乘积，，其中矩阵C中的第ii 行第 jj列元素可以表示为：
如下所示：
我们知道斐波那契数列的递推公式f(i)=f(i−1)+f(i−2)f(i)=f(i−1)+f(i−2)
因此我们可以写出以下式子
f(i)=1×f(i−1)+1×f(i−2)f(i)=1×f(i−1)+1×f(i−2)
f(i−1)=1×f(i−1)+0×f(i−1)f(i−1)=1×f(i−1)+0×f(i−1)
将每一项的系数写成一个矩阵
[1110][1110]
由矩阵乘法的特性可知
[f(i)f(i−1)]=[1110]×[f(i−1)f(i−2)][f(i)f(i−1)]=[1110]×[f(i−1)f(i−2)]
由此可推出（或找规律）
[f(n)f(n−1)]=[1110]n−1×[f(1)f(0)]=[1110]n−1×[10][f(n)f(n−1)]=[1110]n−1×[f(1)f(0)]=[1110]n−1×[10]
因此只要计算出[1110]n−1[1110]n−1 ，然后取左上角值就可以了
矩阵定义如下：
struct matrix {int n;int m;long long a[SIZE][SIZE];matrix() {n=2;m=2;memset(a,0,sizeof(a));}matrix(int x,int y) {//构造函数n=x;m=y;memset(a,0,sizeof(a));}void print() {for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {printf("%d ",a[i][j]);}printf("\n");}}void setv(int x) {//矩阵初始化if(x==0) {memset(a,0,sizeof(a));}if(x==1) {memset(a,0,sizeof(a));for(int i=1; i<=n; i++) a[i][i]=1;}}friend matrix operator *(matrix x,matrix y) {//矩阵乘法matrix tmp=matrix(x.m,y.m);for(int i=1; i<=x.n; i++) {for(int j=1; j<=y.m; j++) {tmp.a[i][j]=0;for(int k=1; k<=y.n; k++) {tmp.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod;
// tmp.a[i][j]%=mod; 取模次数太多会TLE！ }tmp.a[i][j]%=mod;}}return tmp;}
};矩阵快速幂：
（跟整数的快速幂几乎一样）
matrix fast_pow(matrix x,int k) {matrix ans=matrix(2,2);ans.setv(1);while(k>0) {if(k&1) {ans=ans*x;}k>>=1;x=x*x;}return ans;
}