题目链接

算法竞赛进阶指南-22.奇数码问题

Method : 归并排序

空格左(右)移动时，逆序对数量显然不发生变化；空格上(下)移动时，相当于某个数与它前(后)n - 1个数交换了位置，因为${n -1}$是偶数，所以逆序对数的变化也只能是偶数。

把除了空格(也就是0)以外的数据放在n * n的一维数组中，然后统计逆序对的个数，判断逆序对个数的奇偶性是否相同。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL a, b, p;

LL fast_pow(LL x, LL n) {
    LL res = 1LL;
    while (n) {
        if (n & 1) {
            res = res * x % p;
        }
        x = x * x % p;
        n = n >> 1;
    }
    return res % p;
}

int main() {
    cin >> a >> b >> p;
    cout << fast_pow(a, b) << endl;
    return 0;
}

复杂度分析

• 时间复杂度${O(log_2n)}$， 其中$log_2n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度${O(1)}$。

上面的结论还可以扩展到n * m个数码的问题，此时需要对列数m分奇偶讨论:

• 当m为奇数，需要判断"两个局面的逆序对数"的奇偶性是否相同
• 当m为偶数，需要判断"两个局面的逆序对数之差"和“两个局面下空格所在行数之差”的奇偶性是否相同