POJ 1026 Cipher置換群

テーマは
1~nの置換シーケンスを与え、次いで整数kと列を与える
k回置換後の串はどうなっているかを聞く.
まず,与えられた列の長さはn以下であり,不足した位置にスペースを補う.
そしてk回置換すると、直接置換を繰り返すのではなく、置換内の各サイクルに一定の長さがあるため、この長さの置換回数を超えると必ず前のある状態と同じになるので、各サイクルについて、長さがlenであれば、サイクル内のメタセルはk%len回置換するだけでよい.
初めて置換群の概念を見て、思わず前の1つの問題を思い出して、1組の無秩序な数を与えて、任意の2つの数の間で互いに位置を交換することができて、少なくとも何回交換して昇順の状態に達することを聞いて、それでは明らかに1つの置換の問題で、問題の中で循環する個数を要求するだけで、要素の個数-循環の個数で求めました.では,問題が隣接する2つの数しか交換できないことを要求すると,木状配列や集計ソートの問題である.

/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 1100
#define INF 1000000000
#define eps 1e-7
#define PI 3.1415926535898
using namespace std;
int n, k, a[205], l[205];
char s[205], ans[205];
void zhihuan()
{
    for(int i = 1; i <= n; i++)
    {
        int t = a[i];
        int cnt = 1;
        while(t != i)
        {
            cnt++;
            t = a[t];
        }
        l[i] = cnt;
    }
}
int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        zhihuan();
        while(scanf("%d", &k) != EOF && k)
        {
            getchar();
            gets(s + 1);
            int len = strlen(s + 1);
            for(int i = len + 1; i <= n; i++)
                s[i] = ' ';
            s[n + 1] = '\0';
            for(int i = 1; i <= n; i++)
            {
                int pos = i;
                for(int j = 0; j < k % l[i]; j++)
                    pos = a[pos];
                ans[pos] = s[i];
            }
            ans[n + 1] = '\0';
            puts(ans + 1);
        }
        puts("");
    }
    return 0;
}