矩阵乘法经典应用之置换

矩阵乘法经典应用之置换

学习用矩阵做置换的过程很有趣，我遇到的置换问题最开始的思路就向矩阵发展了，然而很不幸，那题时间卡的紧，用矩阵是超时的做法（反正我没过）。不过我也意外的学习了这样的方法：

经典的置换矩阵：

比如：1 2 3 4 ---> 2 4 1 3

设转换矩阵是A。给出置换方法：

表示第

位置上的字符换到i位置上所以

通过将置换操作分离出来成快速幂，最后和被操作序列做乘法，缩短时间。估计时间：O(nm) --> O(logn+m)

这是那一道题（注：下面的代码是超时的，我只是想用用矩阵模拟置换而已）

POJ 1026 Cipher

​​http://poj.org/problem?id=1026​​

输入： 10 4 5 3 7 2 8 1 6 10 9 1 Hello Bob 1995 CERC

解释：

n

k  string

给出置换方法：

.  表示第i位置上的字符换到

位置上

所以

。

#include #include #include using namespace std;const int N=205;int n;char mys[N],cont[N];struct matrix{ int m[N][N];}I;int add(int a,int b){ int ans=0; while(b){ if(b&1) ans=ans+a; a=a+a; b>>=1; } return ans;}matrix operator *(const matrix a,const matrix b){ matrix ans; for(int i=0;i>=1; } return ans;}void show(matrix mp){ for(int i=0;i

下面才是正确的解法：

对置换群每个元素寻找循环节。

#include #include #include using namespace std;const int N=205;int a[N];int cir[N];char str[N];char ans[N];bool vis[N];int main(){ //freopen("cin.txt","r",stdin); int n; while(scanf("%d",&n)&&n){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); int dex=i; int loop=0; while(vis[dex]==0){ loop++; vis[dex]=1; dex=a[dex]; } cir[i]=loop; } int k; while(scanf("%d",&k)&&k){ memset(ans,0,sizeof(ans)); getchar(); gets(str+1); int len=strlen(str+1); for(int i=1;i<=n;i++){ int d=k%cir[i]; int dex=i; for(int j=0;jlen) ans[dex]=' '; else ans[dex]=str[i]; } ans[n+1]=0; printf("%s\n",ans+1); } printf("\n"); } return 0;}

来一个可以用矩阵置换的：

P1049送给圣诞夜的礼品

​​5 86 1 3 7 5 2 43 2 4 5 6 7 17 1 3 4 5 2 65 6 7 3 1 2 42 7 3 4 6 1 5

解释：

n,m,k

m行n列的置换矩阵

6 1 3 7 5 2 4 就是把6位置上的元素换到1位置上，1位置上的元素换到2位置上…… 经典的置换操作, .粗略的讲就是 B=(1,2,3……n)'

#include #include #include using namespace std;const int N=105;struct matrix{ int m[N][N]; int nn,mm; matrix operator =(const matrix a){ nn=a.nn; mm=a.mm; for(int i=0;i>=1; } return ans;}void show(matrix v){ cout<<"show: "<

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