poj 3233

本文主要是介绍poj 3233，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        这题是矩阵相乘，由于k很大，所以要借用整数快速幂（如果不会快速幂可以参看我之前的博文）的方法计算矩阵的相乘，所以方法与之前的差不多，如果这个会了，题目就不难了。这道题有更高级的方法，但是我用的是普通的方法，也能AC，适合初学者。

        这道题我主要是写了矩阵相乘、相加和n次方，这不难理解。这道题用了一个小技巧，就是用struct“包装”了二维数组，这样返回矩阵和赋值将会更简单。

代码（C++）：

#include <cstdlib>
#include <iostream>using namespace std;struct matrix{int x[30][30];   
};int n,m;
matrix mx;matrix multi_matrix(matrix m1,matrix m2)
{int i,j,k;matrix tmp;memset(tmp.x,0,sizeof(tmp.x));for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++){tmp.x[i][j]=(tmp.x[i][j]+m1.x[i][k]*m2.x[k][j])%m;}                     }}return tmp;
}matrix add_matrix(matrix m1,matrix m2)
{int i,j;matrix tmp;memset(tmp.x,0,sizeof(tmp.x));for(i=0;i<n;i++){for(j=0;j<n;j++){tmp.x[i][j]=(m1.x[i][j]+m2.x[i][j])%m;}}return tmp;
}matrix pow_matrix(int k)
{int i,j;matrix ans,tmp; tmp=mx;for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j) ans.x[i][j]=1;else ans.x[i][j]=0;}}while(k){if(k&1){ans=multi_matrix(ans,tmp);  }k>>=1;tmp=multi_matrix(tmp,tmp);} return ans;
}matrix sum(int k)
{     if(1==k) return mx;matrix tmp,t;tmp=sum(k/2);if(k%2==0){return add_matrix(multi_matrix(pow_matrix(k/2),tmp),tmp);      }else{  t=pow_matrix(k/2+1);    return add_matrix(add_matrix(multi_matrix(t,tmp),tmp),t);}
}int main(int argc, char *argv[])
{int k,i,j; matrix tmp;cin>>n>>k>>m;for(i=0;i<n;i++){for(j=0;j<n;j++){cin>>mx.x[i][j];mx.x[i][j]%=m;}}tmp=sum(k);for(i=0;i<n;i++){for(j=0;j<n;j++){if(j!=0) cout<<' ';cout<<tmp.x[i][j];}cout<<endl;}       system("PAUSE");return EXIT_SUCCESS;
}

题目：

Description

Input

Output

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

这篇关于poj 3233的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---