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

核心逻辑与数学原理

归并排序求逆序对

逆序对定义为满足 $i < j$ 且 $A[i] > A[j]$ 的二元组 $(i, j)$。 暴力解法是 $O(N^2)$的。

归并排序中，基于分治思想，将序列 $A[l..r]$ 划分为 $A[l..mid]$ 与 $A[mid+1..r]$。 在执行归并（Merge）操作的双指针线性扫描阶段，若满足 $A[p_2] < A[p_1]$，由于左序列已保证升序排列，则 $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$ 唯一表示为：

$$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$，则将当前的底数 $a$ 累乘至全局答案并取模。 将指数 $b$ 右移一位（$b \leftarrow b \gg 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。

模板

归并排序求逆序对

// long long 避免溢出
long long cnt = 0; 

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

    int mid = l + ((r - l) >> 1); // 位运算替代除法，防溢出且加速

    // 1. 分治：向下切割问题规模
    merge_sort(a, temp, l, mid);
    merge_sort(a, temp, mid + 1, r);

    // 2. 归并：双指针线性扫描
    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++];
            // 此时左序列剩余元素全部对 a[j] 产生逆序贡献，一次性批量累加
            cnt += (mid - i + 1); 
        }
    }

    // 3. 扫尾与数组回填
    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
    a %= m;                // 防止初始底数 a >= m 导致后续乘法直接起步溢出

    while (b > 0) {
        if (b & 1) {
            // 当前位有效，累乘至答案
            ans = ans * a % m; 
        }
        a = a * a % m; // 底数倍增升级
        b >>= 1;       // 指数右移，规模折半
    }
    return ans;
}

NOIP 实战避坑指南

逆序对计数器爆 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 存储计数器，否则直接整型溢出沦为负数。

快速幂乘法爆 long long 与特判 $m=1$

• 乘法溢出边界：在不使用 __int128 的情况下，普通的 a * a % m 只能安全承受 $m \le 3 \times 10^9$ 的数据范围（如常见的 $10^9+7$）。若题目给出的模数 $m$ 达到 $10^{18}$ 级别，两个 long long 直接相乘会爆 64 位整型，此时必须改用“ O(\log m) 的快速乘（龟速乘）”算法进行拆分取模。
• 特判 $m=1$ 盲点：当题目给出的特判数据中模数 $m=1$ 时，根据模运算定义，任何数对 $1$ 取模的结果都必须为 $0$。若代码中盲目将答案初始化为 ans = 1，会导致 $m=1$ 的测试点全部判错。因此，初始化答案必须规范写作 ans = 1 % m。

经典 NOIP/洛谷 真题

洛谷 P1908 逆序对

• 题意描述：给定一个长度为 $N$ 的序列，求其中逆序对的总数。$N \le 5 \times 10^5$，序列中元素 $A[i] \le 10^9$。
• 问题本质与核心思路：最纯粹的逆序对模板题。由于 $N \le 5 \times 10^5$，无法使用 $O(N^2)$ 的暴力枚举。元素大小 $A[i] \le 10^9$ 虽大，但归并排序只依赖元素的相对大小比较，天然免疫大数值，无需像树状数组解法那样进行繁琐的离散化预处理。 在双指针线性合并时，利用左子序列的升序特性批量累加贡献，时间复杂度 $O(N \log N)$。

核心代码

long long cnt = 0; // 全局计数器，防止极端单调降序下答案爆 int

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++];
            // 核心：由于左序列升序，a[i] 爆了则 i 到 mid 的所有元素均对 a[j] 产生逆序贡献
            cnt += (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];
}

洛谷 P1226 【模板】快速幂

• 题意描述：给你三个整数 $a, b, p$，求 $a^b \pmod p$ 的值。$a, b, p \le 2 \times 10^9$。
• 问题本质与核心思路：考察大指数下的模运算优化。核心思路是将指数 $b$ 进行二进制按位拆分（减治思想），将原问题收敛至 $O(\log b)$ 次乘法。根据数据范围，模数 $p \le 2 \times 10^9$，乘法中间结果最大约为 $(2 \times 10^9)^2 = 4 \times 10^{18}$，恰好在标准 long long 的安全上限（约 $9 \times 10^{18}$）以内。 此外，必须警惕 p = 1 的特判边界。

核心代码

long long quick_pow(long long a, long long b, long long p) {
    long long ans = 1 % p; // 防坑点：若 p=1，任何数取模的结果必须为 0
    a %= p;                // 防坑点：规避初始 a >= p 导致第一次乘法直接溢出的风险

    while (b > 0) {
        if (b & 1) {
            ans = ans * a % p; // 只要 p <= 2*10^9，long long 乘法绝无溢出风险
        }
        a = a * a % p; // 底数倍增升级
        b >>= 1;       // 指数右移，问题规模折半
    }
    return ans;
}