这段时间学了些关于快速(*)的东西，及时复习一下以免忘记
快速幂
求(b^pmod k)，其中(p)是个很大的数，比如……(10^{100})
暴力就t了，所以我们考虑
如果(p)是偶数，那么(b^p=b^{p/2} imes b^{p/2})
如果(p)是奇数，那么(b^p=b^{p/2} imes b^{p/2} imes b)
这个过程可以一直下去，最后时间复杂度就是(O(log(p)))的
Code
s=1;
while (p)
{
if (p&1)s=s*b%k;
b=b*b%k;
p>>=2;
}
快速(龟速)乘
求(a imes b mod k)，其中(a,b)都是长整型数，也就是说相乘就会爆(long long)
怎么办呢，我们仍然考虑和快速幂一样的思路
如果(b)是偶数，那么(a imes b=a imes (b/2)+ a imes(b/2))
如果(b)是奇数，那么(a imes b=a imes(b/2)+a imes(b/2)+a)
这个过程跟快速幂很类似，虽然时间是(O(log(b)))的，但很好的避免了爆$long long $的问题
不过话虽这么说，多个大常数很容易使程序t掉，所以如果不得已最好不要用快速乘
Code
s=0;
while (b)
{
if (b&1)s=(s+a)%k;
a=a*2%k;
b>>=1;
}
口胡代码，有错见谅
矩阵快速幂
给你一个方阵(A)，求(A^k mod p)
既然是快速幂，那肯定避免不了乘法，首先我们要了解矩阵乘法的定义
设(A,B)是两个矩阵，(C=A imes B)那么
-
(A)的列数必须和(B)的行数相等
-
如果(A)是(n imes r)的矩阵，(B)是(r imes m)的矩阵，那么(C)是一个(n imes m)的矩阵
-
(C_{i,j}=sum_{k=1}^{r}A_{i,k} imes B_{k,j})
-
根据运算过程，显然矩阵乘法只有结合律没有交换律
而对于矩阵的乘幂来说，只有方阵，即行列个数相等的矩阵，可以进行乘幂运算
在此，我们还需要了解一个概念——单位矩阵
主对角线上的元素都是(1)，通常用(I)或(E)表示，图长这样子
这个东西可是非常的有用，任何数乘它都等于那个数本身，相当于线性运算中的(1)
然后矩阵快速幂就很好写出来啦
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int n,k,p=1e9+7,a[500][500],s[500][500],b[500][500];
void jzc(int x[500][500],int y[500][500])
{
memset(b,0,sizeof(b));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
b[i][j]=(b[i][j]+x[i][k]*y[k][j])%p;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
x[i][j]=b[i][j];
}
signed main()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>a[i][j],s[i][i]=1;
while (k)
{
if (k&1)jzc(s,a);
jzc(a,a);
k>>=1;
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<s[i][j]<<" ";
cout<<endl;
}
return 0;
}
可能还会有其他的一些快速(*)，以后学了会补充上。咕咕咕