首页 > 代码库 > 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