模运算优化

在计算机科学与算法竞赛中，模运算优化（Mod Optimization）是处理超大整数运算、避免数值溢出以及降低常数级时间复杂度的核心技术。本笔记将系统化地解析模运算的数学原理、代码实现机制、乘法逆元的应用，并结合具体的仿射变换问题（如 Fancy 序列）展示其在实际工程和算法中的落地应用。

---

1. 什么是模运算

给定一个模数 MOD，表达式 $x \bmod MOD$ 表示“ $x$ 除以 MOD 后的余数”。在主流编程语言中，这通常通过取模运算符 % 来实现（例如 x % MOD）。

示例：

$$17 \bmod 5 = 2$$

因为 $17 = 5 \cdot 3 + 2$。

---

2. 引入模运算的核心动因

在算法设计中，要求对结果进行 % MOD 操作通常基于以下两大原因：

• 防止数值呈指数级爆炸： 连续的加法、乘法、幂运算或动态规划状态转移会导致数值快速增长。即使部分高级语言（如 Python）原生支持大整数，处理极大数字时也会消耗更多内存，且算术运算的时间成本会显著上升。
• 满足等价类计算需求： 许多组合数学或计数问题只关心“模意义下的结果”。根据模运算的数学性质，在计算的每一步都进行取模，最终结果与算出真实大数后再取模是等价的。

---

3. 模优化的本质

核心原则： 模优化并非仅仅在算法的最后一步执行 % MOD，而是将所有可能导致数值爆炸的中间运算，始终限制在给定的模空间内进行。

错误的做法是将表达式计算出极其巨大的中间结果后再取模。正确的做法是步步取模：

# 推荐的模优化运算过程
x = (x + y) % MOD
x = (x * z) % MOD

---

4. 模运算的基本数学性质

假设模数为 $M$，以下是模空间内的核心运算定律：

• 加法定理： $$(a+b) \bmod M = ((a \bmod M)+(b \bmod M)) \bmod M$$

• 减法定理： $$(a-b) \bmod M = ((a \bmod M)-(b \bmod M)) \bmod M$$

• 乘法定理： $$(a \cdot b) \bmod M = ((a \bmod M) \cdot (b \bmod M)) \bmod M$$

注意：模空间下不能直接应用普通的除法律，除法需要引入“乘法逆元”的概念。

---

5. 时间复杂度优化的微观原理

模优化通常不会改变算法的大 O 渐进复杂度（例如将 $O(n^2)$ 降为 $O(n \log n)$），但它能极大地优化常数级时间。

• 不取模的代价： 若不断执行 x *= 10**9，变量会逐渐变为超长整数。大整数的算术运算时间复杂度与数字的位数正相关，导致循环内部的单次操作越来越慢。
• 取模的收益： 只要始终保持 $0 \le x < MOD$，变量的值域就永远被固定在常量范围内。这保证了 CPU 进行加减乘除时的内存稳定性和 $O(1)$ 的理想执行速度。

---

6. 常数 10**9 + 7 的应用背景

在多数算法题中，通常规定 MOD = 10**9 + 7。选择该常数的原因包含：

• 具备大质数特性： 质数作为模数带来了一个极其关键的代数性质——除了 0 之外，模空间内的所有数都存在乘法逆元，从而使得模除法得以顺利进行。
• 防止整型溢出： 两个接近 10**9 + 7 的数字相加或相乘，其结果在很多语言中能够安全地存入 64 位整型（如 C++ 的 long long）中，避免了硬件级溢出。
• 哈希冲突率低： 足够大的质数能有效降低信息映射时的冲突概率。

---

7. 模运算的核心陷阱：禁止直接除法

在常规算术中，使用 / 或 // 进行除法是理所应当的。然而，在模空间中：

$$\frac{a}{b} \pmod{MOD}$$

绝对不等于 (a % MOD) // (b % MOD)。

在模空间中，“除以 $b$”的代数含义是寻找一个整数 $x$，使得：

$$b \cdot x \equiv a \pmod{MOD}$$

为了求解 $x$，必须利用 $b$ 的乘法逆元 $b^{-1}$，将其转化为乘法运算：

$$x \equiv a \cdot b^{-1} \pmod{MOD}$$

---

8. 乘法逆元（Multiplicative Inverse）

8.1 严谨定义

如果在模 $M$ 意义下，存在一个整数 $b$，使得以下同余式成立：

$$a \cdot b \equiv 1 \pmod M$$

那么 $b$ 即可称为 $a$ 在模 $M$ 下的乘法逆元，记作 $a^{-1}$。

8.2 存在条件

一个数 $a$ 在模 $M$ 下存在逆元的充分必要条件是：$a$ 与 $M$ 互质（即 $\gcd(a, M) = 1$）。由于算法中通常选取大质数作为 $M$，因此区间 $[1, M-1]$ 内的所有整数必然都拥有逆元。

8.3 费马小定理（Fermat's Little Theorem）

当 $M$ 为质数，且 $a$ 不能被 $M$ 整除时，满足：

$$a^{M-1} \equiv 1 \pmod M$$

等式两边同除以 $a$（提取出一个 $a$），可得：

$$a \cdot a^{M-2} \equiv 1 \pmod M$$

因此，逆元 $a^{-1}$ 的直接计算公式为 $a^{M-2} \bmod M$。

---

9. 快速幂与内建 pow 函数

在 Python 中，求解 $a^b \bmod M$ 有两种常见写法，其性能差异巨大：

写法	执行逻辑	性能表现
(a ** b) % M	先在内存中展开计算出极其巨大的整数 $a^b$，最后再执行一次取模运算。	极低。当 $b$ 极大时，会引发严重的内存占用和时间延迟。
pow(a, b, M)	内部采用快速幂算法（二分求幂），在每次执行平方操作时立刻进行取模。	极高。始终处理小规模整数，时间复杂度严格控制在 $O(\log b)$。

结合费马小定理，求解逆元的标准代码实现应为：

def inv(a, MOD):
    return pow(a, MOD - 2, MOD)

---

10. 案例解析：仿射变换序列（Fancy 序列）的模优化

以记录序列并支持全局加法、全局乘法、单点查询的系统为例，探讨模优化的实战应用。

10.1 全局状态的维护

当对整个序列执行仿射变换 $x \rightarrow x \cdot mult + add$ 时，全局的 $mult$ 和 $add$ 必须时刻处于模空间内以防止数值爆炸：

• 全局加法： _add = (_add + inc) % MOD
• 全局乘法： _add = (_add * m) % MOD 以及 _mult = (_mult * m) % MOD

10.2 状态快照与单点还原

插入新元素时，记录当前的全局状态（base_add 和 base_mult）作为快照。查询该元素时，需要计算从插入时刻到当前时刻，该元素额外经历的变换倍率（this_mult）和加法偏移（this_add）。

• 倍率还原（使用模除法）： 要求解 $\frac{current_mult}{base_mult}$，不能使用整除，必须利用逆元：

$$this_mult = current_mult \cdot base_mult^{-1} \pmod{MOD}$$

• 偏移还原：

$$this_add = (current_add - base_add \cdot this_mult) \pmod{MOD}$$

10.3 完整规范代码

MOD = 10**9 + 7

class Fancy:
    def __init__(self):
        self._mult = 1
        self._add = 0
        self._seq = []

    def append(self, val: int) -> None:
        # 将输入值归入模空间，并记录当前仿射变换快照
        self._seq.append((val % MOD, self._add, self._mult))

    def addAll(self, inc: int) -> None:
        self._add = (self._add + inc) % MOD

    def multAll(self, m: int) -> None:
        # 注意：加法偏移量也必须同等放大
        self._add = (self._add * m) % MOD
        self._mult = (self._mult * m) % MOD

    def getIndex(self, idx: int) -> int:
        if idx >= len(self._seq):
            return -1

        val, base_add, base_mult = self._seq[idx]

        # 核心：使用 pow() 计算 base_mult 的乘法逆元
        this_mult = self._mult * pow(base_mult, MOD - 2, MOD) % MOD
        this_add = (self._add - base_add * this_mult) % MOD

        return (val * this_mult + this_add) % MOD

---

11. 常见思维误区与工程陷阱

• 遗漏中间变量取模： 误认为只有最终的 return 语句才需要取模，导致状态累计时触发大整数拖慢性能。
• 滥用整除符号： 在需要还原比例时错误地写下 a // b。务必条件反射地将其替换为 a * inv(b) % MOD。
• 忽视 0 没有逆元： 如果全局乘数变成了 0，计算逆元 pow(0, MOD - 2, MOD) 将失去代数意义。必须在系统设计中针对乘以 0 的情况进行特判。
• 负数取模未归一化： 尽管部分语言（如 Python）的取模会自动处理负数，但在 C++、Java 中，(a - b) % MOD 可能产生负数。更安全的通用模板是 (a - b + MOD) % MOD。

---

12. 模优化通用代码模板（速记版）

建议在处理复杂的模运算系统时，封装如下纯函数：

MOD = 10**9 + 7

def add_mod(a, b):
    return (a + b) % MOD

def sub_mod(a, b):
    return (a - b + MOD) % MOD

def mul_mod(a, b):
    return (a * b) % MOD

def pow_mod(a, b):
    return pow(a, b, MOD)

def inv(a):
    return pow(a, MOD - 2, MOD)

def div_mod(a, b):
    return (a * inv(b)) % MOD