矩阵快速幂专题

传送门：SWPU 2017暑假专题训练-矩阵快速幂

矩阵快速幂专题

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;
const int MOD=2147493647;
ll n,A,B;
#define maxn 7
#define mod(x) ((x)%MOD)

struct mat{
	ll m[maxn][maxn];
}unit;

void init_unit(){
	for(int i=0;i<maxn;i++)
		unit.m[i][i]=1;
	return ;
}

mat operator * (mat a,mat b){
	mat ret=unit;
	ll x;
	for(int i=0;i<maxn;i++)
		for(int j=0;j<maxn;j++){
			x=0;
			for(int k=0;k<maxn;k++){
				x+=mod(a.m[i][k]*b.m[k][j]);
				x=mod(x);
			}
			ret.m[i][j]=x;
		}
	return ret;
}

mat pow_mat(mat a,ll x){
	mat ret=unit;
	while(x){
		if(x&1) ret=ret*a;
		a=a*a;
		x/=2;
	}
	return ret;
}


int main(){
	ll t;
	init_unit();
	scanf("%lld",&t);
	ll c[7][7]={1,1,0,0,0,0,0,
				2,0,0,0,0,0,0,
				1,0,1,0,0,0,0,
				4,0,4,1,0,0,0,
				6,0,6,3,1,0,0,
				4,0,4,3,2,1,0,
				1,0,1,1,1,1,1};
	mat a;
	for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			a.m[i][j]=c[i][j];
			//cout<<"a.m["<<i<<"]["<<j<<"]="<<a.m[i][j]<<endl;
		}
	}
	while(t--){
		scanf("%lld%lld%lld",&n,&A,&B);
		ll res;
		if(n==1) res=A;
		else if(n==2) res=B;
		else{
			mat b;
			b.m[0][0]=B,b.m[0][1]=A,b.m[0][2]=16,b.m[0][3]=8,b.m[0][4]=4,b.m[0][5]=2,b.m[0][6]=1;
			mat ret=pow_mat(a,n-2);
			ret=b*ret;
			res=ret.m[0][0];
		}
		printf("%lld\n",res);
	}
	
	return 0;
}

B.HDU 6030

C.POJ 3070

斐波那契显然可以用矩阵快速幂来解决。

主要问题就是构造矩阵。

（F1，F0）=（1,0）；

（F2，F1）=（？，？）=（F1,F0）*(1 1

1 0)

也就是F2=1*F1+1*F0,F1=1*F1+0*F0;

同理，F3=1*F2+1*F1，F2=1*F2+0*F1.

所以说，矩阵快速幂专题

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD=10000;
#define mod(x) ((x)%MOD)

struct mat{
	int m[2][2];
}unit;

mat operator * (mat a,mat b){
	mat ret;
	ll x;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			x=0;
			for(int k=0;k<2;k++){
				x+=mod(1ll*a.m[i][k]*b.m[k][j]);
				x=mod(x);
			}
			ret.m[i][j]=x;
		}
	}
	return ret;
}

void init_unit(){
	for(int i=0;i<2;i++)
		unit.m[i][i]=1;
}

mat mat_pow(mat a,ll x){
	mat ret=unit;
	while(x){
		if(x&1) ret=ret*a;
		a=a*a;
		x/=2;
	}
	return ret;
}

int main(){
	ll x;	
	init_unit();
	mat a;
	a.m[0][0]=1;	
	a.m[0][1]=1;	
	a.m[1][0]=1;	
	a.m[1][1]=0;
	while(~scanf("%lld",&x)){
		if(x==-1) break;
		int res;
		if(x==0) res=0;
		else{
			mat b=mat_pow(a,x-1);
			res=b.m[0][0];
		}
		printf("%d\n",res);
	}
	return 0;
}

相关推荐