题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1439

题解:

如果直接模拟的话,必定超时。

我们假设对于第i位字符,经过ti次置换后,又回到第i位上,可知2ti,3ti等等过后也会再次回到第i位,我们把ti称为一个周期。

如果我们求得每一位的周期,就可以很方便的求得第k次置换后的结果必然与k%ti的结果一样。

置换群:

数学上,一个置换群是一个群G,其元素是一个给定集M的置换,而其群作用是G中的置换(可以看作是从M到自身的双射)的复合;其关系经常写作(G,M)。注意所有置换的群是对称群;置换群通常是指对称群的一个子群。n个元素的置换群记为Sn;若M 是任意有限或无限集合,则所有M的置换组成的对称群通常写作Sym(M)。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1439.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 200;
int num[N + 5], org[N + 5][N + 5], ord[N + 5];
char input[N + 5], output[N + 5];

void solve(int n) {
    memset(ord, 0, sizeof(ord));
    for (int i = 0; i < n; ++i) org[0][i] = i;
    int idx = 1, tmp = n;
    while (tmp) {
        for (int i = 0; i < n; ++i)
            if (!ord[i]) org[idx][num[i]] = org[idx - 1][i];
        for (int i = 0; i < n; ++i)
            if (!ord[i] && org[idx][i] == org[0][i]) {
                ord[i] = idx;
                --tmp;
            }
        ++idx;
    }
    return;
}

int main() {
    int n;
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            --num[i];
        }
        solve(n);
        int m;
        while (scanf("%d%*c", &m), m) {
            gets(input);
            for (int i = strlen(input); i < n; ++i) input[i] = ' ';
            for (int i = 0; i < n; ++i) output[i] = input[org[m % ord[i]][i]];
            output[n] = '\0';
            puts(output);
        }
        printf("\n");
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/5748 - 海胖博客