高效算法：利用归并排序与快速幂技术求解逆序对与模运算

核心逻辑与数学原理

归并排序求逆序对

逆序对定义为满足 $i < j$ 且 $A[i] > A[j]$ 的二元组 $(i, j)$。基于分治思想，将序列 $A[l..r]$ 划分为 $A[l..mid]$ 与 $A[mid+1..r]$。在合并（Merge）双指针扫描时，若左序列指针 $p_1$ 指向的元素大于右序列指针 $p_2$ 指向的元素，由于左序列已然有序，则 $A[p_1..mid]$ 中的所有元素均大于 $A[p_2]$。此时，跨越两部分的逆序对数量增加贡献值：

$$ \Delta = mid - p_1 + 1 $$

总时间复杂度 $O(N \log N)$，空间复杂度 $O(N)$。

位运算快速幂

求解 $a^b \pmod m$，若线性递推复杂度为 $O(b)$，在 $b \le 10^{18}$ 级别时必 TLE。基于二进制拆分，将 $b$ 表示为：

$$ b = \sum_{i=0}^{k} c_i \cdot 2^i \quad (c_i \in {0, 1}) $$

因此：

$$ a^b = \prod_{i=0}^{k} a^{c_i \cdot 2^i} $$

利用倍增思想，每次迭代令 $a \leftarrow a^2 \pmod m$。若当前二进制最低位 $b \& 1 = 1$，则将当前权值累乘至答案。时间复杂度 $O(\log b)$，空间复杂度 $O(1)$。

算法推导与状态设计

归并排序求逆序对推导

分治过程满足递归式：

$$ T(N) = 2T\left(\frac{N}{2}\right) + O(N) $$

解得 $T(N) = O(N \log N)$。合并时设置双指针 $i = l, j = mid + 1$。

1. 若 $A[i] \le A[j]$：$A[i]$ 归位，无逆序对产生，$i \leftarrow i + 1$。
2. 若 $A[i] > A[j]$：$A[j]$ 归位，意味着 $A[i]$ 及其右侧至 $mid$ 的所有元素均与 $A[j]$ 构成逆序对。计数器 $ans \leftarrow ans + (mid - i + 1)$，$j \leftarrow j + 1$。

快速幂位运算推导

令 $ans = 1 \pmod m$。循环条件为 $b > 0$：

1. 检查最低位：if (b & 1) $\Rightarrow$ $ans = ans \cdot a \pmod m$。
2. 底数自乘倍增：$a = a \cdot a \pmod m$。
3. 指数右移一位：b >>= 1。

C++ 标准源码

#include <iostream>
#include <vector>

using namespace std;

// 归并排序求逆序对，全局变量或传递引用避免复制开销
long long inverse_pairs_count = 0;

void merge_sort(vector<int>& a, vector<int>& temp, int l, int r) {
    if (l >= r) return;

    int mid = l + ((r - l) >> 1); // 防止溢出，位运算加速

    merge_sort(a, temp, l, mid);
    merge_sort(a, temp, mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            // 致命踩坑点：必须转换成 long long 防止加和溢出，此处一次性累加左区间剩余元素个数
            inverse_pairs_count += (mid - i + 1); 
        }
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];

    for (i = l; i <= r; ++i) {
        a[i] = temp[i];
    }
}

// 位运算快速幂
long long quick_pow(long long a, long long b, long long m) {
    long long ans = 1 % m; // 致命踩坑点：若 m=1，答案必须为 0，1%1=0
    a %= m; // 防止初始 a 大于 m 导致后续乘法直接溢出
    while (b > 0) {
        if (b & 1) {
            ans = (__int128)ans * a % m; // 使用 __int128 防止两 long long 相乘爆 64 位时溢出
        }
        a = (__int128)a * a % m;
        b >>= 1;
    }
    return ans;
}

int main() {
    // 优化标准输入输出流，切断与 stdin/stdout 的同步，提升 IO 效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n);
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    merge_sort(a, temp, 0, n - 1);
    cout << inverse_pairs_count << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 逆序对计数器爆 int 极限情况下，长度为 $N$ 的逆序序列，其逆序对数量为 $\frac{N(N-1)}{2}$。在 NOIP 数据范围 $N = 5 \times 10^5$ 时，最大逆序对数约为 $1.25 \times 10^{11}$，远超 int 的 $2 \times 10^9$ 上限。必须使用 long long 存储计数器，否则直接整型溢出沦为负数。
2. 快速幂乘法爆 long long 且未对 $1$ 取模 当模数 $m \approx 10^{18}$ 时，两个 long long 类型数据相乘会达到 $10^{36}$，直接导致 64 位寄存器溢出。在 Linux 64位环境下，必须引入 __int128 进行强制类型转换后再取模。此外，当输入 $b=0$ 且 $m=1$ 时，若直接返回 $1$ 将导致判错，初始化答案须写作 1 % m。

经典 NOIP/洛谷 真题

洛谷 P1908 逆序对

• 题意描述：给定一个长度为 $N$ 的序列，求其中逆序对的总数。$N \le 5 \times 10^5$，$A[i] \le 10^9$。
• 问题本质与核心思路：最纯粹的逆序对模板题。由于数据范围较大，无法使用 $O(N^2)$ 的暴力枚举。核心解题思路为利用归并排序的分治性质，在 $O(N \log N)$ 的时间复杂度内，通过双指针合并有序子序列的同时计算出跨越两半部分的逆序对。

洛谷 P1226 【模板】快速幂

• 题意描述：给你三个整数 $a, b, p$，求 $a^b \pmod p$ 的值。$a, b, p \le 2 \times 10^9$。
• 问题本质与核心思路：考察指数爆炸下的模运算处理。核心思路是将大指数 $b$ 进行二进制按位拆分，将指数运算转化为 $O(\log b)$ 次乘法。每次利用 $b \ \& \ 1$ 检查当前二进制位是否为 $1$，动态维护底数的平方倍增值。