塔子哥の视频带读讲解

算法常识-大彻大悟之取模操作 (opens new window)

1.为什么有些题目会需要你对答案取模？

一般见于计数题，即让你统计方案数的题目。例如:

P1133 百度-2023.03.28-第二题-染色の数组 (opens new window)

P1099 蚂蚁-2023.03.21-第三题-塔子哥的排列权值之和 (opens new window)

这是由于最终的答案非常大，我们直接计算答案会导致整数溢出，计算机无法直接存储。这个时候有些同学可能会说了：那直接大数模拟不就完了吗？

这样从理论上来讲当然没错，但是会有以下两个问题:

1.从编码复杂性来说，除了python，其他语言实现大数模拟非常麻烦。特别要支持乘和除操作。整个模拟算法写下来就已经200行了，那还要不要写题目了？这样对非python选手也是非常不公平的事情。笔试总共就俩小时，写个大数模拟就一个小时过去了（估计还有相当一部分同学都写不出乘法和除法的模拟算法），那就不要玩了。

2.从算法复杂度上来说，当我们要计算的数过大，例如$10^{100000}$ 这种级别，每做一次加法就是$1e5$的复杂度，乘法和除法就到了$1e10$ 次计算了，1秒都算不完了！

综上，我们出这种题目的重点还是在考察大家的数学推导能力，而不是大数模拟能力，所以需要引入取模操作！

2.取模能对吗？

对数字敏感的同学可能马上会反映过来：取模操作并不是双射的！可能存在冲突啊？

例如模数$mod = 6$ ， $9$与$3$ 在$mod\ 6$ 意义下都是$3$ . 那就不对呀。也就是你没办法百分百确定取模之后相同的结果在之前是不是一样的啊

对，没错！取模就是可能出现这种情况，不管怎么样都可能出错，但是听我讲完：我们通常使用$1e9+7$ ， 这是一个大质数。它有这么几个比较好的性质能够尽可能的减少发生错误(冲突)的可能 :

1.数字足够大，那么随机选择一个数$x$，其是$1e9+7$ 的倍数的概率小于刚才我们所选取的$6$ 。

2.$1e9+7$ 虽然大，但是两个这么大的数相乘的时候，恰好不会爆$long\ long$. 所以大，但是大的恰到好处。如果再取更大的数，会导致乘法取模的过程中发生溢出。

3.由于是质数$p$，那么$a\times n , p \nmid a$ 的循环节长度是$p$ ， 而非质数的循环节长度会短于其本身的大小。

4.由于是质数$p$ , 模$p$的环是无零因子环，这意味着任意两个非$p$倍数的数相乘不等于零。那么在连乘的情况下，非质的模数下冲突的概率会大大增加。

这里举个例子，例如$mod\ 6$ , 假设答案只可能是偶数，那么结果就只有可能是$0,2,4$ , 但是如果$mod\ 5$ , 那么结果可以是$2,4,1,3$。冲突概率减小。

总而言之，言而总之就是一句话：取模的确会导致冲突，但是恰当的模数能够让发生错误(冲突)的概率足够小到中彩票，使得我们能够接受这种错误。

同时，你也可以理解为:取模是一种在无法使用大数模拟的情况下的最佳权衡之际。

3.取模实现

看到这里，我们明白了为什么要取模。但是千万不要以为我们下次遇到取模的题目就能写对了。这里面有一车需要注意的错误！ 以下各操作以伪代码形式给出。在文章末尾附有各语言取模模板

0.理解取模

实际上取模操作是一种整数划分。取模操作将所有整数划分到不同的类中。

例如$mod\ 5$ 意义下，任意整数都会被划分到$\{0,1,2,3,4\}$ 这几个类。

例如:$5 \rightarrow 0$

$13 \rightarrow 3$

$-1 \rightarrow 4$

$-2 \rightarrow 3$

$-3 \rightarrow 2$

...

1.加法

def add (a , b , mod):
	a %= mod
	b %= mod
	res = (a + b) % mod
	return res

这个操作没啥好讲的，比较显然。先对$a,b$ 进行取模的原因是保证不溢出。因为考虑如下情况:$a=b=LONG\_MAX$ , 那么$a+b$ 就已经溢出了。对一个已经溢出的数进行取模肯定是错误的了。

2.减法

def sub (a , b , mod)
	a %= mod
	b %= mod
	res = (a - b + mod) % mod
	return res

$a-b$ 可能是负数，但是结果一定 $> -mod$ 。所以我们需要加上一个 $mod$ 来调整到$[0,mod-1]$。

ps:如果$a-b$ 是非负数，那么加一个$mod$再取$mod$对结果无影响。

3.乘法

def mul (a , b , mod)
	a %= mod
	b %= mod
	res = a * b % mod
	return res

$JavaScript$的注意事项:

如果你使用的$JavaScript$ 并且$mod = 1e9+7$ , 那么不能直接这么乘。因为$Js$的最大整数是$1e15$ , 两个$x,y < 1e9+7$ 的数相乘可能会超过最大整数。所以需要上快速乘，具体看底部代码模板实现细节！

4.除法

除法不能直接$a/b \% mod$. 这里需要引入逆元的概念:寻找$x$满足$xb \equiv 1 (mod\ p)$，我们称$x$为$b$的逆元。之后将 除$b$操作 转成$a*x$

逆元理解

例如我们要求解$5/3\% 7$ , 不能直接除3，那我们转而找一个数$x$ ，使得$3*x\%7=1$ 。 $x = 5$

这样的话，$5$其实就可以看作是$3$ 在$mod\ 7$ 意义下的逆元 。

如何寻找一个数$y$的逆元？

一个直观的想法是枚举$i \in [0,mod-1]$ ， 一个一个测试看是否满足$i*y\%p=1$。

当然这样的做法太朴素了，显然不可行...而且逆元也不总是存在。对这一块十分感兴趣的话，可以进一步学习OI Wiki - 费马小定理 (opens new window)

如果你没这么多兴趣，那你只需要知道的是：在$1e9+7$的模数下，逆元一定存在，且$y$的逆元就是$y^{mod-2}$ .当然直接求$y^{1e9+5}$ 肯定是也不现实的，复杂度太大。这里你需要在学习一个算法：快速幂详解 (opens new window)

总结

至此，对于$a/b\%mod$ 可以根据费马小定理，利用快速幂算法先求$b$的逆元 $b^{mod-2}$ ，转成乘法$a*b^{mod-2}\%mod$ 。

def fast_pow (a , b , mod):
	base = a
	ans = 1
	while (b != 0):
		if (b & 1) ans = mul(ans , base , mod)
		base = mul(base , base)
		b >>= 1
	return ans
def div (a , b , mod):
	a %= mod
	b %= mod
	inv_b = fast_pow(b , mod - 2 , mod)
	res = mul(a , inv_b)
	return res 

4.取模模板

接下来以P1320 塔子哥の取模操作练习题 (opens new window)一题为例，给出各语言取模模板！

• C++
• Java
• Python
• Go
• JavaScript

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
// -----取模操作模板----- 建议使用long long 实例化，最稳
template <typename T>
class Mod{
public:
	T add (T x , T y , T mod){
		x %= mod;
		y %= mod;
		T res = (x + y) % mod;
		return res;
	}
	T sub (T x , T y , T mod){
		x %= mod;
		y %= mod;
		T res = (x - y + mod) % mod;
		return res;
	}
	T mul (T x , T y , T mod){
		x %= mod;
		y %= mod;
        T res = x * y % mod;
        return res;
	}
	T div (T x , T y , T mod){
		x %= mod;
		y %= mod;
        T inv = fastPow(y , mod - 2 , mod);
        T res = mul(x , inv , mod);
        return res;
	}
private:
	T fastPow (T a , T b , T mod){
        T ans = 1 , base = a;
        while (b){
            if (b & 1) ans = mul(ans , base , mod);
            base = mul(base , base , mod);
            b >>= 1;
        }
        return ans;
	}
};
// -----取模操作模板 end-----
int main (){
	int n;
    Mod<long long> t;
	cin >> n;
	for (int i = 1 ; i <= n ; i++){
		int op;
		long long x , y;
		cin >> op >> x >> y;
		if (op == 1){
            cout << t.add(x , y , mod) << endl;
		}else if (op == 2){
            cout << t.sub(x , y , mod) << endl;
		}else if (op == 3){
            cout << t.mul(x , y , mod) << endl;
		}else {
            cout << t.div(x , y , mod) << endl;
		}
	}
}

import java.util.*;
// 取模模板
class Mod {
    public long add(long x, long y, int mod) {
    	x %= mod;
    	y %= mod;
    	long res = (x + y) % mod;
        return res;
    }
    
    public long sub(long x, long y, int mod) {
    	x %= mod;
    	y %= mod;
    	long res = (x - y + mod) % mod;
        return res;
    }

    public long mul(long x, long y, int mod) {
    	x %= mod;
    	y %= mod;
    	long res = x * y % mod;
        return res;
    }
    public long div(long x, long y, int mod) {
    	x %= mod;
    	y %= mod;
    	long inv = fastPow (y , mod - 2 , mod);
    	long res = mul(x , inv , mod); 
        return res;
    }
    
    private long fastPow(long a, long b, int mod) {
        long ans = 1;
        long base = a;
        while (b != 0) {
            if (b % 2 == 1) ans = mul(ans, base, mod);
            base = mul(base, base, mod);
            b /= 2;
        }
        return ans;
    }
}

public class Main {
    static final int mod = 1000000007;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Mod t = new Mod();
        for (int i = 1; i <= n; i++) {
            int op = scanner.nextInt();
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            if (op == 1) {
                System.out.println(t.add(x, y, mod));
            } else if (op == 2) {
                System.out.println(t.sub(x, y, mod));
            } else if (op == 3) {
                System.out.println(t.mul(x, y, mod));
            } else {
                System.out.println(t.div(x, y, mod));
            }
        }
    }
}

class Mod:
    def add(self, x, y, mod):
        x %= mod
        y %= mod
        res = (x + y) % mod
        return res
    def sub(self, x, y, mod):
        x %= mod
        y %= mod
        res = (x - y + mod) % mod
        return res

    def mul(self, x, y, mod):
        x %= mod
        y %= mod
        res = (x * y) % mod
        return res

    def div(self, x, y, mod):
        x %= mod
        y %= mod
        inv = self.fastPow(y, mod - 2, mod)
        res = (x * inv) % mod
        return res

    def fastPow(self, a, b, mod):
        ans = 1
        base = a
        while b:
            if b & 1:
                ans = (ans * base) % mod
            base = (base * base) % mod
            b >>= 1
        return ans
mod = 10**9 + 7
t = Mod()
n = int(input())
for i in range(1, n+1):
    op, x, y = map(int, input().split())
    if op == 1:
        print(t.add(x, y, mod))
    elif op == 2:
        print(t.sub(x, y, mod))
    elif op == 3:
        print(t.mul(x, y, mod))
    else:
        print(t.div(x, y, mod))

欢迎补充

特别注意,与其他语言不同的是，js的最大整数为$2^{53}-1 \approx 9e15$ ,那就意味着$1e9+7$这个模数下即使是正确的取模方式，相乘操作也会导致溢出。所以所有乘法需要替换成快速乘 来将乘法转加法，这样就一定不会溢出。

由于$O(1)$的乘法我们使用快速乘代替(实现类似于快速幂)，那么我们的总复杂度也需要乘上一个$log\ mod \approx 31$ 的常数。具体看代码！

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const mod = 1000000007;

    class Mod {
        add(x, y, mod) {
            x %= mod;
            y %= mod;
            let res = (x + y) % mod;
            return res;
        }
        sub(x, y, mod) {
            x %= mod;
            y %= mod;
            let res = (x - y + mod) % mod;
            return res;
        }
        // not correct for js!
        /*mul(x, y, mod) {
            x %= mod;
            y %= mod;
            let res = (x * y) % mod;
            return res;
        }*/
        // fast mul is correct
        mul(a, b, mod) {
            let ans = 0;
            let base = a;
            while (b) {
                if (b & 1) ans = this.add(ans, base, mod);
                base = this.add(base, base, mod);
                b >>= 1;
            }
            return ans;
        }
        div(x, y, mod) {
            x %= mod;
            y %= mod;
            let inv = this.fastPow(y, mod - 2, mod);
            let res = this.mul(x, inv, mod);
            return res;
        }
        fastPow(a, b, mod) {
            let ans = 1;
            let base = a;
            while (b) {
                if (b & 1) ans = this.mul(ans, base, mod);
                base = this.mul(base, base, mod);
                b >>= 1;
            }
            return ans;
        }
    }

    let n = parseInt(lines[0]);
    let t = new Mod();

    for (let i = 1; i <= n; i++) {
        let [op, x, y] = lines[i].split(' ').map(Number);
        if (op === 1) {
            console.log(t.add(x, y, mod));
        } else if (op === 2) {
            console.log(t.sub(x, y, mod));
        } else if (op === 3) {
            console.log(t.mul(x, y, mod));
        } else {
            console.log(t.div(x, y, mod));
        }
    }
});