矩阵快速幂

模板

ll mod;
const int maxMat=5;
struct Mat{
	int n,m;
	ll v[maxMat][maxMat];
	Mat(int n,int m):n(n),m(m){
		init();
	}
	void init(){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				v[i][j]=0;
	}
	Mat operator*(Mat &b)const{
		Mat c(n,b.m);
		c.init();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=b.m;j++)
				for(int k=1;k<=m;k++){
					c.v[i][j]+=v[i][k]*b.v[k][j];
					c.v[i][j]%=mod;//koko
				}
		return c;
	}
	void print(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				cout<<v[i][j]<<" ";
			cout<<endl;
		}
	}
};
Mat unit(maxMat-1,maxMat-1);
void init(){
	memset(unit.v,0,sizeof(unit.v));
	for(int i=1;i<=maxMat-1;i++)
		unit.v[i][i]=1;
}
Mat fp(Mat a,ll n){
	Mat res=unit;
	res.n=res.m=a.n;
	while(n){
		if(n&1)
			res=res*a;
		a=a*a;
		n>>=1;
	}
	return res;
}

常用递推式