快速幂
第1题 快速幂 查看测评数据信息
求a的n次幂，答案模1000000007。
输入格式
一行，两个整数，a和n。1<=a<=1000, 1<=n<=1000000000。
输出格式
一个整数
输入/输出例子1
输入：
2 4
输出：
16
样例解释
无
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1000000007;
int a, n;
int qpow(int a, int k)
{
int res=1;
while (k>0)
{
if (k&1) res=(res*a)%Mod;
a=(a*a)%Mod;
k>>=1;
}
return res;
}
signed main()
{
scanf("%lld%lld", &a, &n);
printf("%lld", qpow(a, n));
return 0;
}
比较简单，就是注意拆二进制拆的是k
快速幂递归的写法会超时，以后都用进制拆分的做！
重载运算符
矩阵快速幂
一些常识
矩阵一般用大写字母表示，矩阵的元素用大括号括住，例如：
矩阵快速幂用途
1.加速递推
2.矩阵的多少多少次方在图论的一个含义
矩阵加减法
前提：行列相等
规则：对应运算加减，例如：
由于减法是加法的逆运算，也支持交换律和结合律
数乘
重点-矩阵快速幂
矩阵乘法
假设，矩阵A*矩阵B=矩阵C
进行矩阵乘法的前提条件：A的列数=B的行数（这里后面会解释为什么）
有一个规律，C的行数：A的行数， C的列数：B的列数，我们可以最后再回来看为什么，先往下看
计算规则：
矩阵A的第i行和矩阵B的第j列相乘（对应元素相乘后相加），所得的结果放在矩阵C的第i行第j列
可能直接看有点生硬，我们画个图理解下。A矩阵有大小是2*2，B矩阵大小是1*2，根据计算规则
A的第1行 * B的第1列，我们要对应元素相乘，也就是每个数依次相乘
就是{1, 2} * {5, 6}，1对应5，2对应6，对应元素相乘后相加，那么就是，1*5+2*6=17，那么C矩阵的第1行第1列的数是17
A的第2行 * B的第1列，{3, 4} * {5，6}，3*5+4*6=39，那么C矩阵第1行第2列的是是39
这个时候，如果你理解的过程，你就会发现，A的行数必须=B的列数，那么才可以计算，不然无法让元素对应上，所以这就是矩阵乘法的规则
我们再观察C的行数，由于A每行乘B每列，会在C每行形成一个数
例如，A的第1行 * B的第1列，会在C第1行形成一个数
那么一般情况，A的第n行 * B的第x列，会在C第n行形成一个数，所以影响C的行数的是A矩阵它有多少行，也就是A的行数
我们再观察C的列数，由于A每行乘B每列，会在C每列形成一个数
例如，A的第1行 * B的第1列，会在C第1列形成一个数
如果我们用 A的第2行 * B的第1列，还是会在在C第1列形成一个数
那么一般情况，A的第x行 * B的第n列，会在C第n列形成一个数
所以C的列数与A的行数无关，只与B的列数有关，也就是B有多少列，C就有多少列
所以说，C的行数：A的行数， C的列数：B的列数
其实这个例子不是特别好，因为列只有1列，你可以试试A矩阵为2*2，B矩阵也为2*2的情况！
伪代码：
for (i~n) 遍历A的行，假设有n行
for (j~m) 遍历B的列，假设有m列
for (k~p) 遍历A的列，假设有p列
c[i][j]+=a[i][k]*b[k][j]
看懂后，这代码应该就显而易见了，由于计算C矩阵的值并不能O(1)算，要每一个元素对应每一个元素，所以得开k这个循环
时间复杂度：O(n^3)
标签：int,矩阵,相乘,行数,列数,对应 From： https://www.cnblogs.com/didiao233/p/18358508