POJ 1721-CARDS（置换群-单个循环置换幂运算倒推）

╰+攻爆jí腚メ 2022-06-17 05:55 168阅读 0赞

CARDS

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;1918</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;983</td> 
  </tr> 
 </tbody> 
</table>

Description

Alice and Bob have a set of N cards labelled with numbers 1 ... N (so that no two cards have the same label) and a shuffle machine. We assume that N is an odd integer.  
The shuffle machine accepts the set of cards arranged in an arbitrary order and performs the following operation of double shuffle : for all positions i, 1 <= i <= N, if the card at the position i is j and the card at the position j is k, then after the completion of the operation of double shuffle, position i will hold the card k.  
  
Alice and Bob play a game. Alice first writes down all the numbers from 1 to N in some random order: a1, a2, ..., aN. Then she arranges the cards so that the position ai holds the card numbered a i+1, for every 1 <= i <= N-1, while the position aN holds the card numbered a1.  
  
This way, cards are put in some order x1, x2, ..., xN, where xi is the card at the i th position.  
  
Now she sequentially performs S double shuffles using the shuffle machine described above. After that, the cards are arranged in some final order p1, p2, ..., pN which Alice reveals to Bob, together with the number S. Bob's task is to guess the order x1, x2, ..., xN in which Alice originally put the cards just before giving them to the shuffle machine.

Input

The first line of the input contains two integers separated by a single blank character : the odd integer N, 1 <= N <= 1000, the number of cards, and the integer S, 1 <= S <= 1000, the number of double shuffle operations.  
The following N lines describe the final order of cards after all the double shuffles have been performed such that for each i, 1 <= i <= N, the (i+1) st line of the input file contains pi (the card at the position i after all double shuffles).

Output

The output should contain N lines which describe the order of cards just before they were given to the shuffle machine.  
For each i, 1 <= i <= N, the ith line of the output file should contain xi (the card at the position i before the double shuffles).

Sample Input

7 4
    6
    3
    1
    2
    4
    7
    5

Sample Output

4
    7
    5
    6
    1
    2
    3

Source

[CEOI 1998][]

题目意思：

每次置换的规则是，a\[i\]变为a\[a\[i\]\]，给出末状态以及置换的次数，求初状态。

解题思路：参考：http://blog.csdn.net/kksleric/article/details/7793397

**单个循环置换幂运算：**

1、循环长度与指数互质时的整幂运算

设T=a，T^k=b，且gcd(L,k)=1，则**b\[i\]=a\[(k+1)\*i%L\]**。由此可以构造出T^k(如L=10，k=3)

![1343370893_7124.png][]

![1343371095_7929.png][]

2、循环长度与指数互质的分数幂运算（开方）

构造方法与上述过程类似但互逆，不过就是目标循环每次指针向后移k位，源循环每次向后移1位罢了。

3、循环长度与指数不互质时，单个循环是不能开方的。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[1010],cnt[1010],b[1010];
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)
        {
            scanf("%d",&a[i]);
            cnt[i]=a[i];
        }
        bool flag=true;
        int res=0;
        while(1)//求循环节
        {
            ++res;
            for(int i=1; i<=n; ++i)
                b[i]=a[a[i]];
            for(int i=1; i<=n; ++i)
                if(cnt[i]!=b[i])
                {
                    flag=false;
                    break;
                }
            if(flag) break;
            flag=true;
            for(int i=1; i<=n; ++i)
                a[i]=b[i];
        }
        for(int i=1; i<=n; ++i)
            a[i]=b[i];
        m=res-m%res;
        for(int i=1; i<=m; ++i)
        {
            for(int j=1; j<=n; ++j)
                b[j]=a[a[j]];
            for(int j=1; j<=n; ++j)
                a[j]=b[j];
        }
        for(int i=1; i<=n; ++i)
            printf("%d\n",a[i]);
        return 0;
    }

[CEOI 1998]: http://poj.org/searchproblem?field=source&key=CEOI+1998
[1343370893_7124.png]: https://img-my.csdn.net/uploads/201207/27/1343370893_7124.png
[1343371095_7929.png]: https://img-my.csdn.net/uploads/201207/27/1343371095_7929.png