矩阵快速幂算法解析

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

struct matrix{

int s[6][6];

}r, d, p, q,tt;

void view(matrix x){

for(int i=0; i<6; i++){

for(int j=0; j<6; j++){

cout<<x.s[i][j]<<" ";

}

cout<<endl;

}

cout<<endl;

}

matrix mult(matrix a, matrix b){

cout<<"a"<<endl;

view(a);

cout<<"b"<<endl;

view(b);

matrix temp;

memset(temp.s, 0, sizeof(temp.s));

for(int i=0; i<6; i++)

for(int j=0; j<6; j++)

for(int k=0; k<6; k++)

temp.s[i][j]=(temp.s[i][j]+a.s[i][k]*b.s[k][j])%10000;

cout<<"a*b"<<endl;

view(temp);

return temp;

}

matrix pow(int n){

matrix temp;

memset(temp.s, 0, sizeof(temp.s));

for(int i=0;i<6;i++)

temp.s[i][i]=1;

cout<<"temp"<<endl;

view(temp);

tt=r;

while(n)

{

if(n%2==0){

tt=mult(tt, tt);

n/=2;

}

else{

temp=mult(tt, temp);

n--;

}

}

return temp;

}

int

main()

{

int n, sum, k=0;

memset(r.s, 0, sizeof(r.s));

memset(d.s, 0, sizeof(d.s));

r.s[0][1]=3;

r.s[0][2]=2;

r.s[0][3]=1;

for(int i=1; i<6; i++)

r.s[i][i-1]=1;

d.s[0][0]=2;

while(cin>>n){

sum=0;

p=pow(n);

cout<<"aaaa"<<endl;

q=mult(p, d);

for(int i=0; i<6; i++){

sum+=q.s[i][0];

}

cout<<"Case "<<++k<<": "<<sum<<endl;

}

return 0;

}

转载于:https://my.oschina.net/dianpaopao/blog/142924