目录

• 「学习笔记」矩阵乘法与矩阵快速幂
  • 矩阵乘
    • 算法
    • 代码
  • 矩阵快速幂
    • 算法
    • 用处
    • 代码（模板题）
  • 练习题
    • 斐波那契数列
      • 思路
      • 代码
    • [SCOI2009] 迷路
      • 思路
      • 代码
    • 佳佳的 Fibonacci
      • 思路
      • 代码
    • 选拔队员（不知道教练从哪里找的）
      • 题意
      • 思路
      • 代码
    • Tr A
      • 思路
      • 代码

const ll N=110,inf=1ll<<40;
ll n,m,p;
class Matrix{
public:
	ll mat[N][N];
	inline ll* operator[](ll x){return mat[x];}
	inline Matrix operator*(Matrix ma)const{
		Matrix mt;
		_for(i,1,n){
			_for(j,1,p){
				mt[i][j]=0;
				_for(k,1,m)mt[i][j]+=mat[i][k]*ma[k][j];
			}
		}
		return mt;
	}
}a,b;
inline void print(Matrix ma){
	_for(i,1,n){
		_for(j,1,p)printf("%lld ",ma[i][j]);
		puts("");
	}
	return;
}
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline void In(){
		n=rnt(),m=rnt();
		_for(i,1,n)_for(j,1,m)a[i][j]=rnt();
		p=rnt();
		_for(i,1,m)_for(j,1,p)b[i][j]=rnt();
		print(a*b);
		return;
	}
}

const ll N=110,P=1e9+7,inf=1ll<<40;
ll n,k;
class Mat{
public:
	ll a[N][N];
	inline ll* operator[](ll x){return a[x];}
	inline void one(){_for(i,1,n)a[i][i]=1;}
	inline Mat operator*(Mat ma){
		Mat mt;
		_for(i,1,n){
			_for(j,1,n){
				mt[i][j]=0;
				_for(k,1,n)mt[i][j]=(mt[i][j]+a[i][k]*ma[k][j]%P)%P;
			}
		}
		return mt;
	}
}a;
inline void printf(Mat ma){
	_for(i,1,n){
		_for(j,1,n)printf("%lld ",ma[i][j]);
		puts("");
	}
	return;
}
inline Mat fpow(Mat ma,ll b){
	Mat ans;ans.one();
	while(b){
		if(b&1)ans=ans*ma;
		ma=ma*ma,b>>=1;
	}
	return ans;
}
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline void In(){
		n=rnt(),k=rnt();
		_for(i,1,n)_for(j,1,n)a[i][j]=rnt();
		printf(fpow(a,k));
		return;
	}
}

const ll N=5,inf=1ll<<40;
ll n,m;
class Mat{
public:
	ll a[N][N];
	inline ll* operator[](ll x){return a[x];}
	friend Mat Mul(Mat m1,Mat m2){
		Mat an;
		_for(i,1,2){
			_for(j,1,2){
				an[i][j]=0;
				_for(k,1,2)an[i][j]=(an[i][j]+m1[i][k]*m2[k][j]%m)%m;
			}
		}
		return an;
	}
};
inline Mat fpow(ll b){
	Mat ans;ans[1][1]=ans[1][2]=1,ans[2][1]=ans[2][2]=0;
	Mat ma;ma[1][1]=ma[1][2]=ma[2][1]=1,ma[2][2]=0;
	while(b>0){
		if(b&1)ans=Mul(ans,ma);
		ma=Mul(ma,ma),b>>=1;
	}
	return ans;
}
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline void In(){
		n=rnt(),m=rnt();
		Mat ans=fpow(n-2);
		printf("%lld\n",ans[1][1]);
		return;
	}
}

const ll N=110,P=2009,inf=1ll<<40;
ll n,m,t,g[N][N];
class Mat{
public:
	ll a[N][N];
	inline ll* operator[](ll x){return a[x];}
	inline void one(){_for(i,1,m)a[i][i]=1;return;}
	inline Mat operator*(Mat ma){
		Mat ans;
		_for(i,1,m){
			_for(j,1,m){
				ans[i][j]=0;
				_for(k,1,m)ans[i][j]=(ans[i][j]+a[i][k]*ma[k][j]%P)%P;
			}
		}
		return ans;
	}
}tu;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline ll rsnt(){
		char c=getchar();
		while(!isdigit(c))c=getchar();
		return (c^48);
	}
	inline Mat fpow(Mat ma,ll b){
		Mat ans;ans.one();
		while(b){
			if(b&1)ans=ans*ma;
			ma=ma*ma,b>>=1;
		}
		return ans;
	}
	inline void Zhuan(){
		_for(i,1,n){
			_for(j,1,9){
				ll k=10*(i-1)+j;
				tu[k][k+1]=1;
			}
			_for(j,1,n){
				ll k1=10*(i-1);
				ll k2=10*(j-1);
				if(g[i][j])tu[k1+g[i][j]][k2+1]=1;
			}
		}
		return;
	}
	inline void In(){
		n=rnt(),t=rnt();
		_for(i,1,n)_for(j,1,n)g[i][j]=rsnt();
		m=10*n,Zhuan();
		Mat ans=fpow(tu,t);
		printf("%lld\n",ans[1][m-9]);
		return;
	}
}

const ll N=110,inf=1ll<<40;
ll n,m;
class Mat{
public:
	ll a[N][N];
	inline ll* operator[](ll x){return a[x];}
	inline void one(){a[1][1]=a[1][2]=1;}
	inline Mat operator*(Mat ma){
		Mat ans;
		_for(i,1,2){
			_for(j,1,2){
				ans[i][j]=0;
				_for(k,1,2)ans[i][j]=(ans[i][j]+a[i][k]*ma[k][j]%m)%m;
			}
		}
		return ans;
	}
};
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline Mat fpow(Mat ma,ll b){
		Mat ans;ans.one();
		while(b){
			if(b&1)ans=ans*ma;
			ma=ma*ma,b>>=1;
		}
		return ans;
	}
	inline void In(){
		n=rnt(),m=rnt();
		Mat mat;mat[1][1]=mat[1][2]=mat[2][1]=1;
		Mat ans=fpow(mat,n+1);
		printf("%lld\n",(n*ans[1][2]%m-ans[1][1]+m+2)%m);
		return;
	}
}

const ll N=110,inf=1ll<<40;
ll T,m,n;
class Mat{
public:
	ll a[5][5];
	inline ll* operator[](ll x){return a[x];}
	inline Mat operator*(Mat ma){
		Mat ans;
		_for(i,1,2){
			_for(j,1,2){
				ans[i][j]=0;
				_for(k,1,2)ans[i][j]=(ans[i][j]+a[i][k]*ma[k][j]%m)%m;
			}
		}
		return ans;
	}
};
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline Mat fpow(ll b){
		Mat ans;ans[1][1]=ans[1][2]=1,ans[2][1]=ans[2][2]=0;
		Mat ma;ma[1][1]=ma[1][2]=ma[2][1]=1,ma[2][2]=0;
		while(b){
			if(b&1)ans=ans*ma;
			ma=ma*ma,b>>=1;
		}
		return ans;
	}
	inline void In(){
		n=rnt();
		printf("%lld\n",fpow(n)[1][1]%m);
		return;
	}
}

const ll N=20,P=9973,inf=1ll<<40;
ll T,n,k;
class Mat{
public:
	ll a[N][N];
	inline ll* operator[](ll x){return a[x];}
	inline void one(){_for(i,1,n)a[i][i]=1;return;}
	inline void zero(){memset(a,0,sizeof(a));return;}
	inline Mat operator*(Mat ma){
		Mat ans;ans.zero();
		_for(i,1,n){
			_for(j,1,n){
				ans[i][j]=0;
				_for(k,1,n)ans[i][j]=(ans[i][j]+a[i][k]*ma[k][j]%P)%P;
			}
		}
		return ans;
	}
}a;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline Mat fpow(Mat ma,ll b){
		Mat ans;ans.zero();ans.one();
		while(b){
			if(b&1)ans=ans*ma;
			ma=ma*ma,b>>=1;
		}
		return ans;
	}
	inline ll GetAnswer(Mat ma){
		ll num=0;
		_for(i,1,n)num=(num+ma[i][i]);
		return num%P;
	}
	inline void In(){
		n=rnt(),k=rnt();
		a.zero();
		_for(i,1,n)_for(j,1,n)a[i][j]=rnt();
		Mat ans=fpow(a,k);
		printf("%lld\n",GetAnswer(ans));
		return;
	}
}