矩阵乘法和快速幂

2017-11-02

来一波传送门
我个人认为写的很好。
下面是模板

#include<cstdio>
#define ll long long
using namespace std;
#define re register
const int mod=1000000007;
struct base {
	ll w[110][110];
}a;
ll n,k;
base cheng(base a,base b) {
	base ans;
	for(re ll i=1; i<=n; i++)
		for(re ll j=1; j<=n; j++)
			ans.w[i][j]=0;
	for(re ll i=1; i<=n; i++)
		for(re ll j=1; j<=n; j++)
			for(re ll k=1; k<=n; k++)
				ans.w[i][j]+=a.w[i][k]*b.w[k][j],ans.w[i][j]%=mod;
	return ans;
}//矩阵乘法
base pow_kuai(ll k) {
	base ans;
	for(re ll i=1;i<=n;i++){ans.w[i][i]=1;}
	while(k){
		if(k%2){
			ans=cheng(a,ans);
		}
		a=cheng(a,a);
		k/=2;
	}
	return ans;
}//快速幂
int main() {
	scanf("%lld%lld",&n,&k);
	for(re ll i=1; i<=n; i++)
		for(re ll j=1; j<=n; j++) {
			scanf("%lld",&a.w[i][j]);
		}
	base ans=pow_kuai(k);
	for(re ll i=1; i<=n; i++) {
		for(re ll j=1; j<=n; j++)
			printf("%lld ",ans.w[i][j]);
		printf("\n");
	}
	return 0;
}

一道模板题。
斐波那契数列
用矩乘
f[n]=f[n-1]+f[n-2]
f[n-1]=f[n-1]+0*f[n-2]

可以得出
enter description here

 #include<cstdio>
using namespace std;
#define ll long long
#define re register
const int mod=1000000007;
struct base {
    ll w[3][3];
}a,ans;
ll n;
base cheng(base a,base ans) {
    base b;
    for(re ll i=1; i<=2; i++)
        for(re ll j=1; j<=2; j++)
            b.w[i][j]=0;
    for(re int i=1; i<=2; i++)
        for(re int j=1; j<=2; j++)
            for(re int k=1; k<=2; k++)
                b.w[i][j]+=a.w[i][k]*ans.w[k][j],b.w[i][j]%=mod;
    return b;
}
int main() {
    scanf("%lld",&n);
    a.w[1][1]=a.w[2][1]=a.w[1][2]=1;
    ans.w[1][1]=1;
    ans.w[2][1]=1;
    n--;
    while(n){
        if(n%2){
            ans=cheng(ans,a);
        }
        a=cheng(a,a);
        n/=2;
    }
    printf("%lld",ans.w[1][1]);
    return 0;
}