学步园

题意：直接引用潘震皓的论文《置换群快速幂运算》。

[问题描述]

剀剀和凡凡有N张牌（依次标号为1，2，……，N）和一台洗牌机。假设N是奇数。洗牌机的功能是进行如下的操作：对所有位置I（1≤I≤N），如果位置I上的牌是J，而且位置J上的牌是K，那么通过洗牌机后位置I上的牌将是K。

剀剀首先写下一个1~N的排列a_i，在位置a_i处放上数值a_i+1的牌，得到的顺序x₁,x₂, ..., x_N作为初始顺序。他把这种顺序排列的牌放入洗牌机洗牌S次，得到牌的顺序为p₁,p₂, ..., p_N。现在，剀剀把牌的最后顺序和洗牌次数告诉凡凡，要凡凡猜出牌的最初顺序x₁,
x₂,..., x_N。

[输入]

第一行为整数N和S。1≤N≤1000，1≤S≤1000。第二行为牌的最终顺序p₁,p₂, ..., p_N。

[输出]

为一行，即牌的最初顺序x₁,x₂, ..., x_N。

注：在置换群中有一个定理：设，（T为一置换，e为单位置换（映射函数为的置换）），那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。或者有个更一般的结论：设，（T为一循环，e为单位置换），那么k的最小正整数解为T的长度。

[算法分析]

很显然，这题的一副扑克牌就是一个置换，而每一次洗牌就是这个置换的平方运算。由于牌的数量是奇数，并且一开始是一个大循环，所以做平方运算时候不会分裂。所以，在任意时间，牌的顺序所表示的置换一定是一个大循环。

那么根据文章开头提到的定理：设，（T为一循环，e为单位置换），那么k的最小正整数解为T的长度。

可以知道，这个循环的n次方是单位循环，换句话说，如果k mod n=1，那么这个循环的k次方，就是它本身。我们知道，每一次洗牌是一次简单的平方运算，洗x次就是原循环的2^x次方。

因为n是奇数，2^x mod n=1一定有一个<n的整数解，假设这个解是a；那也就是说，一幅牌，洗a次，就会回到原来的顺序。使用最终顺序不停地洗，直到回到原始顺序，求出循环节长度a以后，再单纯地向前模拟a-s次，就可以得到原始顺序了。

上面的算法是出题方给出的标准算法。显然，时间复杂度为O(n²+logs)。

换一个方向：给定了结果和s以后，可以简单地将这个目标置换用3.1节的方法开方s次得到结果。时间复杂度为O(n*s)。

或者可以更简单地，算出2^s，将目标置换直接开2^s次方。这里有一个技巧，因为在开方时只需要在循环中前进2^s次，所以我们只关心(2^s) mod n，也就免去了大数字的运算。所以，计算2^s需要O(logs)，而开方需要O(n)。整个时间复杂度为O(n+logs)。

方法一：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 1100
int p[MAXN];
bool flag[MAXN];

void permute ( int n ) //模拟置换
{
    int now, i, tmp[MAXN];
    memset(flag,0,sizeof(flag));
    for ( i = 1; i <= n; i++ )
    {
        if ( flag[i] ) continue;
        now = i;
        while ( flag[now] == 0 )
        {
            flag[now] = 1;
            tmp[now] = p[p[now]];
            now = p[p[now]];
        }
    }
    for ( i = 1; i <= n; i++ ) p[i] = tmp[i];
}

int mod_exp ( int a, int b, int n )
{
    int ret = 1;
    a = a % n;
    while ( b >= 1 )
    {
        if ( b & 1 )
            ret = ret * a % n;
        a = a * a % n;
        b >>= 1;
    }
    return ret;
}

int main()
{
    int n, s, a, i;
    scanf("%d%d",&n,&s);
    for ( i = 1; i <= n; i++ )
        scanf("%d",&p[i]);
    for ( a = 1; mod_exp(2,a,n) != 1; a++ );
    s = s % a;
    for ( i = 1; i <= a - s; i++ )
        permute ( n );
    for ( i = 1; i <= n; i++ )
        printf("%d\n",p[i]);
    return 0;
}