Petr and Permutations

caoshuchen · 2023-11-02 10:59:47 · 题解

Petr and Permutations

题意

就是有两个序列，开始都是从 1\to n 顺序排列，现在 Petr 对第一个序列进行 3n 次操作，Alex 对第二个序列进行 7n+1 次操作，每次都是将两个数互换位置。

现在给出了最终打乱结果，问是 Petr 打乱的还是 Alex 打乱的，若是 Petr 输出 Petr 否则输出 Um_nik。

思路

如果学过逆序对，最先想到的一般都是它，那么我们就先讲讲它的做法：

我们发现 3n 与 7n+1 的奇偶性不一样，那么这说明，我们只需要找到逆序对的奇偶特征即可，然后再根据 3n 与 7n+1 判断是谁打乱的。

首先我们想到，交换两个数时的情况与对应的奇偶特征，如下：

此时我们发现，对于交换的两个数，小的那个交换后到右边，那么它前面所有一直到它原本的位置（包括原本位置）的所有元素都大于了它，所以要加上这些数，然后发现较大那个也是同理，但注意去重，不要算两次首尾，最终发现，假设交换的两个位置之间夹着的元素个数为 x，那么逆序对增加量为 2x+1 则每次交换，逆序对奇偶性都会发生改变。

这完了吗？不，没完，其实这个证明是错误的！为什么呢？因为还有可能若干个交换的位置互相交叠，如 1,5 换，3,7 换，等等。当两个重叠时还好处理，但到了更多就很难证明了，所以我们使用代数的方法证明，如下：

请观察一下，我们其实可以发现，不关于 a,b 的逆序对是不会改变的，而交换的前后，在这两个元素围出的区间以外，逆序对的个数是不变的，因为在区间之前的元素，大于 a,b 的依然大于，位置也依然小于 a,b 的；在区间之后的元素，小于 a,b 的依然小于，位置也依然大于 a,b 的，所以没有变化。

但在区间内，有什么样的变化呢？我们设：

在 a,b 之间（不包括 a,b）的数的个数为 len

区间内小于 a 的个数为 x，则大于它的个数为 len-x

区间内大于 b 的个数为 y，则小于它的个数为 len-y

那么原本这个区间关于 a,b 的逆序对个数为 x+y 而交换后关于 a,b 的逆序对个数就变为 2len-(x+y) 其实这里我们已经看出来了，它的奇偶性不变，实在不行可以列个表，如下：

所以奇偶性不变，最后别忘了，由于 a,b 交换后，它们之间的逆序对关系也会改变：a>b 时，转换后逆序对减一；a<b 时，转换后逆序对加一。所以最终奇偶性是都会改变的。

所以我们只需要判断逆序对个数的奇偶性是否等于 3n 的奇偶性即可，效率 O(n\log_2n)。

还有一种方法，主要思路来源于 @ pufanyi 的题解（感谢），但证明与推导过程有些差异，再此也是讲一下。

我们如果说能计算出你复原的次数，就可以直接进行判断奇偶性，不用再求逆序对了，因为对于每一种情况，它变换所需要的步数的奇偶性是唯一确定的，为什么呢？我想了一会，没有想到很好的思路，只能再用逆序对的奇偶变换来佐证：

我们想一下，如果说我们已经变出了一个序列，需要 x 步，那么我们只需要不断的重复交换固定的两个元素 2k 次，它的序列就依然会回复成现状，如下：

如果我们转换到这个序列操作次数未用完，那就这样进行若干次这样的操作即可，直到操作次数用完，而我们发现操作次数奇偶性是不会改变的，所以可以直接对它进行判断。

那么会不会说：可以进行奇数次操作变回来呢？如果这样的话，那我们就无法判断是谁打乱而来的了！其实是不会发生的，你想想如果这样的话就没有答案了，谁都有可能，这题就是错题了，但还是给出一个让人信服的证明：

如果进行奇数次操作让它变回来了，那么它的逆序对奇偶性也就变换了奇数次，则最终逆序对奇偶性就发生了改变，那就很明显了：原本你的逆序对个数是奇数，转了一圈回来变偶数了，不可能的嘛。所以通过一个反证，我们说明了这件事。

所以我们只需要知道序列要变换多少次能变回成 1\to n 即可。

我们可以设计一个数组 t 存储每一个值目前所在的位置，然后依次从 1\to n 交换位置 t_i，i 上的数，然后更新 t_{a_i} 与 a_i 即可，如果 t_i = i 那么就不用交换，也不用累计答案，否则就交换并累计，最后再进行判断，看看是谁打乱的即可，效率 O(n)。

Code

思路 1

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000005];
int t[1000005];

int slv(int l, int r) {
    if (l + 1 >= r)
        return 0;
    int mid = (l + r) / 2;
    int ans = (slv(l, mid) + slv(mid, r)) % 2;
    for (int i = l, j = mid; i < mid; i++) {
        while (j < r && a[j] < a[i]) j++;
        ans = (ans + j - mid) % 2;
    }
    int cur = l;
    for (int i = l, j = mid; i < mid; i++) {
        while (j < r && a[j] < a[i]) t[cur++] = a[j++];
        t[cur++] = a[i];
    }
    for (int i = mid; i < r; i++)
        if (a[i] > a[mid - 1])
            t[cur++] = a[i];
    for (int i = l; i < r; i++)
        a[i] = t[i];
    return ans % 2;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    int k = slv(1, n + 1);
    if (k % 2 == n % 2)
        cout << "Petr" << endl;
    else
        cout << "Um_nik" << endl;
    return 0;
}

思路 2

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000005];
int t[1000005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i), t[a[i]] = i;
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (t[i] != i) {
            int ai = a[i];
            k++, swap(a[i], a[t[i]]), swap(t[i], t[ai]);
        }
    }
    if (k % 2 == n % 2)
        cout << "Petr" << endl;
    else
        cout << "Um_nik" << endl;
    return 0;
}