快速降次
我们以快速幂为例子，模拟一下这个过程。
假如我们现在要计算 $2^{13}$。我们可以用 <cmath> 头文件的 pow(2,13) 但是它的效率并不高。我们现在要手写快速幂，让 $2$ 直接乘 $13$ 次是很朴素的方法，快速幂比他快的多。
首先，我们直到如下结论 $x^a\times x^b = x^{a+b}$
所以，$x\times x=x^2$，$x^2\times x^2 = x^4$，$(x^2)^2 = x^4$。
我们知道任何一个数都可以写成二进制数，我们也可以将 $13$，直接写成二进制数表示形式 $13 = 2^3+2^2+2^0 = 8+4+1$（二进制：$1101$）
那么，我们就可以将原式变形 $(((2)^2\times 2)^2)^2\times 2$ 整理一下 $(((2)^2)^2)^2\times ((2)^2)^2\times 2 = 2^8\times 2^4\times 2$。
这样我们就可以边降次，边让辅助乘数快速生长。
辅助乘数（笔者为了方便描述自定义变量）：辅助累计答案的变量，比如上面的例子，辅助乘数初始值 $2$，接着会变换成 $4$（$2^2$），然后是 $8$（$2^3$），而当累计需要时，可以直接取到。（后面代码中的辅助加数，意义相同）
不一定每回都是以 $2$ 次的频率向上升，也可以 $3$，$4$……或更多，根据情况而定即可。不要被模板扼杀了无限的想法！
快速幂
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int m_d=1e9+7;
long long k_m(long long a,long long b){//辅助乘数，乘的次数
long long r_s=1;//结果统计
while(b){
if(b&1)r_s=(r_s*a)%m_d;//可以理解成二进制时，如果当前位为 1，就需要辅助乘数更新结果。
a=(a*a)%m_d;//辅助乘数
b>>=1;//快速降次
}
return r_s%m_d;
}
int main(){
long long a=r_r(),n=r_r();//读入a，n次乘
long long a_s=k_m(a,n);//得到结果
printf("%lld",a_s);//输出
return 0;
}
快速乘
与快速幂道理相似。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int m_d=1e9+7;
long long k_c(long long a,long long b){//辅助加数，乘的次数
long long r_s=0;//结果统计
while(b){
if(b&1)r_s=(r_s+a)%m_d;//更新答案
a=(a+a)%m_d;//辅助加数
b>>=1;//快速降次
}
return r_s%m_d;
}
int main(){
long long a=r_r(),n=r_r();//读入a，加n次
long long a_s=k_c(a,n);//得到结果
printf("%lld",a_s);//输出
return 0;
}
但是，快速乘并非比普通的乘法快，它的主要作用是：有些时候我们会发现直接相乘会都是信息，找到之间的过程，保留这些信息。举个简单的例子，两个马上越界（极大的）的 long long 相乘一定会丢很多东西。
这时候就可以用快速乘，一步一取模。虽然会很慢，但是保留了程序和结果的正确性。（很多时候为了保留信息也不得不用，依据题目而言）
矩阵快速幂
矩阵加
矩阵减
矩阵乘
形状上：2*2 和 2*3 的矩阵乘积后,结果是 2*3 的矩阵。
即 a*b 矩阵 和 c*d 的矩阵乘积结果是 a*d 的矩阵。其中 b 和 c 必须相等。原因看下面。
运算法则：对于结果矩阵的第 i 行第 j 列的位置的结果是由前一个矩阵的对应的行。和后一个矩阵对应的列。对应位置乘积和获得的。
比如第 1 行第 1 列的 11.是由前矩阵的第一行 (1,3) 和后矩阵的第一列 (2,3) 对应位置乘积和。
1*2 + 3*3 = 11 获得的。
如果上述 b 和 c 如果不相等。那么会有地方"失配"没有数值可以进行计算。不符合矩阵乘法定义。
（矩阵还有很多有趣的运算与用途，感兴趣可以自己了解一下，矩阵相乘的的数学意义）。
代码（矩阵快速幂）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int n;
const int o_o=101;
const int m_d=1e9+7;
struct po{
long long a[o_o][o_o];
po(){//初始化数组
memset(a,0,sizeof a);
}
po operator *(const po &x)const{//重载乘号（封装矩阵相乘格式）
po z;
for(int k=1;k<=n;k++)//第一个矩阵的列，第二个矩阵的行
for(int i=1;i<=n;i++)//结果矩阵的行，第一个矩阵的行
for(int j=1;j<=n;j++)//结果矩阵的列，第二个矩阵的列
z.a[i][j]=(z.a[i][j]+a[i][k]*x.a[k][j]%m_d)%m_d;
return z;//返回结果矩阵
}
}a,a_s;
long long k;
void k_j(long long b){
while(b){//可以直接写成快速幂形式，因为已经将矩阵的乘法格式封装好了
if(b&1)a_s=a_s*a;//累计答案
a=a*a;//辅助矩阵增次
b>>=1;
}
}
int main(){
n=r_r();k=r_r();、
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)a.a[i][j]=r_r();//读入初始矩阵
for(int i=1;i<=n;i++)a_s.a[i][i]=1;//初始化答案矩阵
k_j(k);//矩阵快速幂
for(int i=1;i<=n;i++){//输出结果矩阵
for(int j=1;j<=n;j++)
printf("%d ",a_s.a[i][j]);
puts("");
}
return 0;
}
