POJ-3735 线性变换构造矩阵

网友投稿 714 2022-10-20

POJ-3735 线性变换构造矩阵

POJ-3735 线性变换构造矩阵

可以根据题目中所给的每轮操作来构造矩阵.. 自己构造的....结果WA了好几次..后来才发现当是s i j 时,应该将i列和j列整个交换...我自己开始时只交换了s[ i ] [ j ] 与 s [ j ] [ i ] ...囧..为了能做出加法运算..构造出的A矩阵是n+1维的..并且初始值矩阵也是n+1列的={0,0,0,...1} ..关于几种操作构造矩阵的方法.程序里体现得很清楚了..

Program:

#include#include#include#include#define ll long longusing namespace std;struct node{ ll s[110][110]; }h,temp,T,_2M[32];int n,m,k;char c;void Output_Matrix(node a,int n){ int i,j; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) printf("%d ",h.s[i][j]); printf("\n"); } printf("-------------------\n"); return;}node Matrix_Mul(node a,node b,int n){ int i,j,k; memset(temp.s,0,sizeof(temp.s)); for (k=1;k<=n;k++) for (i=1;i<=n;i++) if (a.s[i][k]) for (j=1;j<=n;j++) temp.s[i][j]+=a.s[i][k]*b.s[k][j]; return temp;}node getmatrix(node h,int n,int l){ int i,k,p; _2M[0]=h; k=1; for (p=1;p<=30;p++) { _2M[p]=Matrix_Mul(_2M[p-1],_2M[p-1],n); k*=2; if (k>l) break; } memset(T.s,0,sizeof(T.s)); for (i=1;i<=n;i++) T.s[i][i]=1; while (l) { while (k>l) { k/=2; p--; } T=Matrix_Mul(T,_2M[p],n); l-=k; } return T;}int main(){ int i,x,y,p,z; while (~scanf("%d%d%d",&n,&m,&k)) { if (!n && !m && !k) break; memset(h.s,0,sizeof(h.s)); for (i=1;i<=n+1;i++) h.s[i][i]=1; for (i=1;i<=k;i++) { do { c=getchar(); }while (c<'a' || c>'z'); if (c=='g') { scanf("%d",&x); h.s[n+1][x]++; }else if (c=='e') { scanf("%d",&x); for (y=1;y<=n+1;y++) h.s[y][x]=0; }else if (c=='s') { scanf("%d%d",&x,&y); if (x==y) continue; for (z=1;z<=n+1;z++) { p=h.s[z][x]; h.s[z][x]=h.s[z][y]; h.s[z][y]=p; } } } // Output_Matrix(h,n+1); h=getmatrix(h,n+1,m); node a; memset(a.s,0,sizeof(a.s)); a.s[1][n+1]=1; h=Matrix_Mul(a,h,n+1); // Output_Matrix(h,n+1); printf("%I64d",h.s[1][1]); for (i=2;i<=n;i++) printf(" %I64d",h.s[1][i]); printf("\n"); } return 0;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:HDOJ 1005 - 上周新队员做的题~我也来水水~矩阵乘法的说..
下一篇:Audit4j- 系统审计开发框架
相关文章

 发表评论

暂时没有评论,来抢沙发吧~