#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
