矩阵快速幂模板：
#include<bits/stdc++.h>using namespace std;#define ll long long#define mod 1000000007struct matrix{ll cell[5][5];matrix(ll a=0,ll b=0,ll c=0,ll d=0){cell[0][0]=a;cell[0][1]=b;cell[1][0]=c;cell[1][1]=d;}}one(1,1,1,0);matrix mul(matrix a,matrix b){matrix r;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++){r.cell[i][j]+=a.cell[i][k]*b.cell[k][j]%mod;r.cell[i][j]=r.cell[i][j]%mod;}return r;}matrix matrixpow(ll k){matrix r(1,0,0,1);matrix cm(1,1,1,0);while(k){if(k&1)r=mul(r,cm);cm=mul(cm,cm);k>>=1;}return r;}int main(){ll n;cin>>n;matrix t=matrixpow(n-1);cout<<t.cell[0][0]<<endl;return 0; }聊矩阵快速幂原理之前，我先聊聊结构体内置函数。
在工程代码中，结构体通常用于定义“纯数据”类型，只包含较少的辅助成员函数，而用class定义“拥有复杂行为”的类型。
成员函数我至今为止见过两种。
第一种：
这种实际上就是用一个结构体保存一个函数，之后通过使用结构体来使用这个函数。并且这个结构体内的函数时可以使用该结构体里面的”纯数据“的。
第二种：
在结构体point里定义了一个函数，函数名也叫point，但没有返回值。这样的函数称为构造函数。构造函数是在声明变量时调用的，例如：声明point a,b（1，2）时，分别调用了point()和point(1,2)。注意这个构造函数的两个参数后面都有“=0”字样，其中0为默认值。也就是说，如果没有指明这两个参数的值，就按0处理，因此point()相当于point(0,0)。
现在我们回到此题代码：
struct matrix{ll cell[5][5];matrix(ll a=0,ll b=0,ll c=0,ll d=0){cell[0][0]=a;cell[0][1]=b;cell[1][0]=c;cell[1][1]=d;}}one(1,1,1,0);用计算机表示矩阵，我们通常使用n维数组。
所以我们要在开始的时候定义一个cell[][]二维数组用于存数据。
在这之后再构造一个函数用于传参，输入值。
现在进入正题，先聊聊矩阵快速幂求斐波那契数列的基本原理：
原理如图：
求斐波那契数列，如果用暴力的解法，即通过前两项来求每一项。这样做当数据过大的时候就会导致超时。而使用矩阵快速幂来计算斐波那契数列就可以极大的减少运算次数，从而达到时间优化。
这种代码的核心时矩阵快速幂：
matrix mul(matrix a,matrix b){matrix r;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++){r.cell[i][j]+=a.cell[i][k]*b.cell[k][j]%mod;r.cell[i][j]=r.cell[i][j]%mod;}return r;}matrix matrixpow(ll k){matrix r(1,0,0,1);matrix cm(1,1,1,0);while(k){if(k&1)r=mul(r,cm);cm=mul(cm,cm);k>>=1;}return r;}我们分别聊一下这两个板块，矩阵乘法板块和快速幂板块。
number 1：
矩阵乘法如果不会的自行百度，这里不做解释。
我们看看该子函数的构造
matrix （该函数的返回值是一个matrix类的结构题）mul（函数名）(matrix a（一个参数是matrix类的结构体）,matrix b（另一个参数也是matrix结构体）)
matrix r （定义一个matrix类的结构体 r ，r是输出结构体）
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) { }三个for循环用于实现矩阵乘法。
return r 最后返回矩阵a和b相乘后的结果。
number2 ：
matrix matrixpow(ll k){matrix r(1,0,0,1);matrix cm(1,1,1,0);while(k){if(k&1)r=mul(r,cm);cm=mul(cm,cm);k>>=1;}return r;}这个就是矩阵快速幂的精髓了。
我们要求矩阵 P 的 n-1 次方暴力解就要只是进行n-1次预算（不包括算连个矩阵之间的运算）
但如果用快速幂的化。
我们把 n 用二进制表达出来，上线就是64位数，所以最多进行64次运算，再够大的情况下，快速幂是很高效的。
过程如下：
如果我们要求P的n次方。
在计算机内部，所有的数都是以二进制的形式存储的，所以n可以用某一二进制来表示。
n&1 就是用于判断这一位取或不去，如果是1就取，如果是0就跳。
快速幂里面一定要注意
即每次右移一位之后就要pow一下。这里不能漏！