矩阵快速幂

例题

我们线代课已经讲到矩阵了,自己也终于把之前卡了好久的矩阵快速幂的题过了ヾ(≧▽≦*)o

补充知识

矩阵矩阵乘:矩阵A左乘矩阵B,记作AB;只有A的列数等于B的行数时才可相乘


P1962 斐波那契数列 – 洛谷

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int M=1e9+7;
struct matrix{
	int c[3][3];
	matrix(){//使每次声明matrix的变量时初始化c数组 
		memset(c,0,sizeof(c));
	}
}F,A;
matrix operator*(matrix &a,matrix &b){//重载的乘法运算符*
	matrix t;
	//矩阵乘 
	rep(i,1,2){
		rep(j,1,2){
			rep(k,1,2){
				t.c[i][j]+=a.c[i][k]*b.c[k][j];
                t.c[i][j]%=M;
			}
		}
	}
	return t;
}
void qpow(int n){
	F.c[1][1]=F.c[1][2]=1;
	A.c[1][1]=A.c[1][2]=A.c[2][1]=1;
	//快速幂 
	while(n){
		if(n&1) F=F*A;
		A=A*A;
		n>>=1;
	}
}
void solve(){
	int n;cin>>n;
	if(n<=2){
		cout<<1;
		return;
	}
	qpow(n-2);//只运算n-2次 
	cout<<F.c[1][1];

}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	//int t;cin>>t;while(t--)
	solve();
	return 0;
}

P1939 矩阵加速(数列) – 洛谷

分析&代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int M=1e9+7;
struct matrix{
	int c[4][4];
	matrix(){
		memset(c,0,sizeof(c));
	}
}F,A;
matrix operator*(matrix &a,matrix &b){
	matrix t;
	rep(i,1,3){
		rep(j,1,3){
			rep(k,1,3){
				t.c[i][j]+=(a.c[i][k]%M*b.c[k][j]%M)%M;
                t.c[i][j]%=M;
			}
		}
	}
	return t;
}
void qpow(int n){
    mem(F.c),mem(A.c);
	F.c[1][1]=F.c[1][2]=F.c[1][3]=1;
	A.c[1][3]=A.c[2][1]=A.c[3][2]=A.c[3][3]=1;
	while(n){
		if(n&1) F=F*A;
		A=A*A;
		n>>=1;
	}
}
void solve(){
	int n;cin>>n;
	if(n<=3){
		cout<<1<<endl;//之前因为没换行一直wa(⊙﹏⊙)
		return;
	}
	qpow(n-1);
	cout<<F.c[1][1]<<endl;

}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}

方程【算法赛】 – 蓝桥云课

寒假遇到的,现在学了矩阵快速幂才过……这题一共交了22次

分析

注意

  • 将答案加上模数再取模主要是用于中间结果可能溢出的情况
  • 直接对答案取模则适用于最终结果可以直接表示为ans模M的情况

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int M=1e9+7;
int k;
struct matrix{
	int c[3][3];
	matrix(){
		memset(c,0,sizeof(c));
	}
}F,A;
matrix operator*(matrix &a,matrix &b){
	matrix t;
	rep(i,1,2){
		rep(j,1,2){
			rep(k,1,2){
				t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j]%M)%M;
			}
		}
	}
	return t;
}
void qpow(int n){
    //mem(F.c),mem(A.c);
	F.c[1][1]=2,F.c[1][2]=k;
	A.c[1][1]=0,A.c[1][2]=-1,A.c[2][1]=1,A.c[2][2]=k;
	while(n){
		if(n&1) F=F*A;
		A=A*A;
		n>>=1;
	}
}
void solve(){
	int n;cin>>n>>k;
	if(n==1){
        cout<<k;
        cout<<endl;
		return;
	}
	qpow(n-1);
	cout<<(F.c[1][2]+M)%M<<endl;//就因为这里没取模卡了快一小时

}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}