矩阵乘法+快速幂
- 快速幂可以用来求得$A^n$ => 因为其具有结合律
- 一种新的求斐波那契数列的方法: $O(logn)$
小技巧
sizeof 不能用传进来的指针的名字要用全局变量或者局部变量的数组的名字
矩阵相乘代码模板
- 向量可以扩充为矩阵=>省代码
- 将矩阵乘法看作是一个操作,一种变换
- 系数矩阵中的数应为常量,不能是变量!!
void mul(int c[][N], int a[][N], int b[][N]) //c=a*b
{
static int tmp[N][N]; //临时数组,因为a和c可能是一个数组,不能边改边读
// static 可以省分配空间的时间,但是注意只初始化一次
memset(tmp, 0, sizeof tmp);
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
for (int k = 0; k < N; k ++ )
tmp[i][j] = tmp[i][j] + (LL)a[i][k] * b[k][j];
memcpy(c, tmp, sizeof tmp);
}
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=3;
int a[N][N];
int n,m;
void mul(int c[],int a[],int b[][N])
{
int temp[N]={0};
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
}
memcpy(c,temp,sizeof temp);
}
void mul(int c[][N],int a[][N],int b[][N])
{
int temp[N][N]={0};
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
{
temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
}
memcpy(c,temp,sizeof temp);
}
int main()
{
cin>>n>>m;
int f1[N]={1,1,1};
int a[N][N]={
{0,1,0},
{1,1,1},
{0,0,1},
};
n--;
while (n){
if(n&1) mul(f1,f1,a);
mul(a,a,a);
n>>=1;
}
cout<<f1[2]<<endl;
return 0;
}