给定一个长度为n序列的排列，问改序列是由原序列进行3n还是7n+1次交换得到的

由7n+1-3n=4n+1知道两个数奇偶性不同

那么我们计算序列的奇偶性即可得

 

补一种O（n）的做法

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6  7 int N; 8 const int maxn = 1e6 + 10; 9 int A[maxn];10 11 int main() {12     scanf("%d", &N);13     for (int i = 1; i <= N; i++) {14         scanf("%d", &A[i]);15     }16     int res = 0;17     for (int i = 1; i <= N; i++) {18         if (!A[i]) continue;19         res ^= 1;20         int x = i;21         while (x) {22             int y = A[x];23             A[x] = 0;24             x = y;25         }26     }27     if (res & 1) {28         puts("Um_nik");29     } else {30         puts("Petr");31     }32     return 0;33 }