首页 > 代码库 > POJ 3233
POJ 3233
二分二分二分。。记录二分的点。1600多MS,应该 可以再优化
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int stack[150],sp;int n,M;struct Matrax { int m[35][35];};Matrax operator +( Matrax A, Matrax B){ Matrax ret; for(int i=0;i<n;i++) for(int j=0;j<n;j++) ret.m[i][j]=(A.m[i][j]+B.m[i][j])%M; return ret;}Matrax a,per;void initial(){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%d",&a.m[i][j]); a.m[i][j]%=M; per.m[i][j]=(i==j); } }}Matrax multi(Matrax a,Matrax b){ Matrax c; int k,i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ c.m[i][j]=0; for(k=0;k<n;k++){ c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M; } c.m[i][j]%=M; } } return c;}Matrax Power(int k){ Matrax c,p,ans=per; p=a; while(k){ if(k&1){ ans=multi(ans,p); k--; } else { k/=2; p=multi(p,p); } }/* for(int i=0;i<n;i++){ for(int j=0;j<n;j++) cout<<‘ ‘<<ans.m[i][j]; cout<<endl; }*/ return ans;}int main(){ int k; while(scanf("%d%d%d",&n,&k,&M)!=EOF){ initial(); sp=-1; stack[++sp]=k; while(k!=1){ if(k%2){ k--; stack[++sp]=k; } else{ stack[++sp]=k/2; k/=2; } }/* for(int i=0;i<=sp;i++) cout<<stack[i]<<‘ ‘; cout<<endl;*/ Matrax ans=a; for(int i=sp;i>=1;i--){ if(stack[i]+1==stack[i-1]){ ans=ans+Power(stack[i-1]); } else if(stack[i]*2==stack[i-1]){ ans=ans+multi(ans,Power(stack[i])); } /* for(int s=0;s<n;s++){ printf("%d",ans.m[s][0]%M); for(int t=1;t<n;t++) printf(" %d",ans.m[s][t]%M); printf("\n"); }*/ } for(int s=0;s<n;s++){ printf("%d",ans.m[s][0]%M); for(int t=1;t<n;t++) printf(" %d",ans.m[s][t]%M); printf("\n"); } } return 0;}
POJ 3233
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。