HDU 2371 Decode the Strings 矩阵快速幂求m次置换

题意：给你一个置换和一个字符串 按照置换m次之后的结果 求原字符串

思路：构造一个矩阵1的每一行只有1个1 a[i][j]代表第i个字母替换成了第j个字母 然后快速幂

#include <cstdio>
#include <cstring>
const int maxn = 88;
struct Mat
{
    int a[maxn][maxn];
};
Mat A, B;
int n, m;
Mat get(Mat x, Mat y)
{
    Mat z;
    memset(z.a, 0, sizeof(z.a));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
            {
                z.a[i][j] += x.a[i][k]*y.a[k][j];
                //z.a[i][j] %= 2;
            }
    return z;
}
void Mat_pow(int x)
{
	//puts("s");
	if(x <= 0)
		return;
    while(x)
    {
        if(x&1)
            B = get(B, A);
        A = get(A, A);
        x >>= 1;
    }
}

int main()
{
	while(scanf("%d %d", &n, &m) && (n+m))
	{
		memset(A.a, 0, sizeof(A.a));
		memset(B.a, 0, sizeof(B.a));
		for(int i = 1; i <= n; i++)
		{
			int x;
			scanf("%d", &x);
			A.a[x][i] = 1;
			B.a[i][i] = 1;
		}
		Mat_pow(m);
		
		char str[1000];
		getchar();
		gets(str+1);
		//puts(str+1);
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(B.a[i][j] == 1)
				{
					printf("%c", str[j]);
					break;
				}
			}
		}
		puts("");
	}
	return 0;
}

HDU 2371 Decode the Strings 矩阵快速幂求m次置换,布布扣,bubuko.com

HDU 2371 Decode the Strings 矩阵快速幂求m次置换

原文：http://blog.csdn.net/u011686226/article/details/22917103