首页 > 代码库 > HDU 2371
HDU 2371
知道了怎么置换之后,就可以用矩阵来置换了,但这道题一直关于置换的地方读不明白。
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int Maxn=100;int pn[Maxn],xn[Maxn],bn[Maxn];int ansp[Maxn];char str[Maxn];struct Matrax { int m[Maxn][Maxn];};int n,m;Matrax per,a;void initial(){ memset(per.m,0,sizeof(per.m)); for(int i=0;i<n;i++){ per.m[i][i]=1; } memset(a.m,0,sizeof(a.m)); for(int i=0;i<n;i++) a.m[pn[i]][i]=1;}Matrax multi(Matrax ae,Matrax b){ Matrax c; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ c.m[i][j]=0; for(int k=0;k<n;k++){ c.m[i][j]+=ae.m[i][k]*b.m[k][j]; } } } return c;}Matrax quick(int k){ Matrax ans=per; Matrax p=a; while(k){ if(k&1){ ans=multi(ans,p); } k=k>>1; p=multi(p,p); } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0) break; for(int i=0;i<n;i++){ scanf("%d",&bn[i]); bn[i]--; xn[i]=i; } for(int i=0;i<n;i++) //为什么要加这个,我想不明白,只好跟着别人加了 pn[bn[i]]=i; getchar(); gets(str); initial(); Matrax ans=quick(m); for(int i=0;i<n;i++){ ansp[i]=0; for(int k=0;k<n;k++) ansp[i]+=xn[k]*ans.m[k][i]; } for(int i=0;i<n;i++) cout<<str[ansp[i]]; cout<<endl; } return 0;}
HDU 2371
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。