闪电彬彬

2021-06-14 21:36 字节跳动_直播server_高级开发工程师

关注

AK F.*ing leetcode 流浪计划之取模

字节员工，直播业务长期招人（北京，杭州，上海，深圳），hc巨多，社招，校招，实习都有。
欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

@[toc]

一、简介

取模是一个数学基础运算，它是一个操作工具，就像平时的加减乘除运算一样。运用时与题目本身的思路没有太大的关系。最基础的是加法取模(a+b)%m = (a%m+b%m)%m(m是正整数)，由此可以衍生出减法取模，乘法取模公式。

当题目中出现类似 由于答案可能会很大，方案数需要对 10^9 + 7 取余 的提示时就要用到这种算法。

由于答案很大，不可能把答案算出来以后再对m取模，所以要逐步求解并取模，保证中间过程一直在整数可表示范围内。

取模的原理虽然很简单，如果不熟练掌握，往往在编写代码时出现越界等情况。

二、公式证明

公式 1

(a+b)%m = (a%m+b%m)%m

证明：

设 a = q1m+r1, b=q2\m+r2, q1, q2, r1, r2为整数, 且 0<=r1,r2<m。

则(a+b)%m =(q1m+r1 + q2\m+r2)%m = ((q1+q2)*m + r1+r2)%m = (r1+r2)%m

(a%m+b%m)%m = ((q1m+r1)%m + (q2\m+r2)%m)%m = (r1+r2)%m

由此可知两式相等。

推广到一般情况当有多个项相加时也成立 这个在解题中应用非常多，可以将整体拆分成逐一求解并取模的形式。

公式2

(a-b)%m = (a%m-b%m)%m

与公式1同理可以证明

公式3

(a*b)%m = (a%m)*(b%m)%m

设 a = q1m+r1, b=q2\m+r2, q1, q2, r1, r2为整数, 且 0<=r1,r2<m。

则(a*b)%m = ((q1m+r1) * (q2\m+r2))%m = (q1*m*q2*m + q1*m*r2 + q2*m*r1 +r1*r2) %m = （r1*r2) %m

(a%m)*(b%m)%m = ((q1m+r1)%m) \ ((q2*m+r2)%m)%m = (r1%m)*(r2%m)%m = （r1*r2) %m

由此可知，公式3成立。

由公式3也可以推出(a^b)%m = ((a%m)^b)%m

三、作用

两数a,b 相加（相减）取模m。此时a, b比较大，相加会超出int表示范围，m较小。
两数a, b 相乘取模m。此时a*b超出int范围，m范围较小。
取模查询，枚举出所有取模情况并保存。待查询使用。
进制转化，并取模m。一般进制转化完后是一个大数，但是m较小。
大数取模m, 类似于作用4，m较小。
方法数求解，一般来说题目中出现这么一行字 由于答案可能会很大，方案数需要对 10^9 + 7 取余，总方法数很大，但是取余后小。

四、注意事项及优化

加（减）法取模

(a+b)%m = (a%m+b%m)%m

运用该公式时，2*m一定要小于整数可表示范围，既最大为2^63-1

多数情况下，2*m 一般是小于2^31-1.

使用时要注意取模结果为负数问题

乘法取模

(a*b)%m = (a%m)*(b%m)%m

运用该公式时，2*m一定要小于整数可表示范围，既最大为2^63-1

多数情况下，2m 一般是小于2^31-1，此时(a%m)\(b%m) < 2^63-1, 可以使用长整型来表示。

但是，如果 m *m> 2^63-1 时，就不能直接相乘。

要把a*b 转化成，a+a+a+...+a， b个a相加，把乘法转化成加法来做。

如果直接相加，复杂度是 O(b) , 最大可达2^6?，不可接受。需要优化。

可以使用倍增算法解决。
$ $a*b= \begin{cases} (2*a)*(b/2), &if\ b\ is\ even\\ (2*a)*(b/2) + a, &if\ b\ is\ odd \end{cases}$ $
通过上式可以把b逐渐变小并转化成加法，复杂度是log(b)。代码如下

/*
倍增算法求解乘法，复杂度log(b)
 */
func multMod(a, b, m int) int {
    sum := 0
    a %= m
    for b > 0 {
        if b&1 == 1 { // odd
            sum = (sum + a) % m
        }
        a = (a + a) % m // a不停地倍增
        b /= 2 // b不停地缩小
    }

    return sum
}

五、牛刀小试

练习1 加法取模应用斐波那契数列

题目链接 https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

题目大意

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

题目解析

利用加法取模公式
F(N) = (F(N - 1)%m + F(N - 2)%m)%m

AC代码

func fib(n int) int {
    if n < 2 {
        return n
    }
    m := int(1e9 + 7)
    f := make([]int, n+1)
    f[0], f[1] = 0, 1
    for i := 2; i <= n; i++ {
        f[i] = (f[i-1] + f[i-2]) % m
    }

    return f[n]
}

练习2 取模查询可被三整除的最大和

题目链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/

题目大意

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

题目解析

朴素的做法是对数组构造出所有的子集，查看子集之和对3取模是否为0。满足条件最大的值。复杂度为O(n^2), 此处n太大了，不合适用。

其实这里可以01背包算法。

设dp(i, j) 为前i个数字可以组成并对3取模得到j的最大数字。

每来一个数字可以考虑选择可不选择当前数字。进行转移。

Dp[len(nums)][0] 就是最终答案。

Dp[0][0]=0

Dp[0][1]=-1 // -1代表不存在的意思

Dp[0][2]=-1 // -1代表不存在的意思

Dp[i][j] = max(dp[i-1][j], dp[i-1][s] + nums[i]) (s = (j - nums[i])%3)，dp[i-1][s]!=-1

AC代码

func max(a,b int) int {
    if a>b {return a}
    return b
}


func maxSumDivThree(nums []int) int {
    dp := make([][]int, len(nums)+1)
    for i:=range dp {
        dp[i] = make([]int, 3)
    }

    dp[0][0]=0
    dp[0][1]=-1
    dp[0][2]=-1
    for i, v:=range nums {
        for j:=0;j<3;j++ {
            dp[i+1][j]=dp[i][j] // 默认可以不选择当前数字

            s := ((j - v)%3 +3) %3 // 防止出现负数
            if dp[i][s]<0 { // 无解
                continue
            }

            dp[i+1][j] = max(dp[i+1][j], dp[i][s]+v)
        }
    }

    return dp[len(nums)][0]
}

练习3 取模查询和可被 K 整除的子数组

题目链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/

题目大意

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

题目解析

利用前缀和公式。

Sum(i,j) = pre[j]-pre[i-1]

要想sum(i,j)%K=0, 则 pre[j]%K = pre[i-1]%K

只要枚举每个pre[j] 查询前面有多少个 pre[i-1]%K = pre[j]%K

注意处理取模负数的情况

AC代码

/*
前缀和
*/
type PreSum struct {
    preSum []int // 数组 preSum[i]=arr[0]+arr[1]+...+arr[i]。
}

// 常用有3种：
// 初始化数据, 通过arr, 初始化preSum
func (ps *PreSum) InitPre(arr []int) {
    ps.preSum = make([]int, len(arr))
    for i, v := range arr {
        if i == 0 {
            ps.preSum[0] = v
        } else {
            ps.preSum[i] = ps.preSum[i-1] + v
        }
    }
}

// 查询区间和
func (ps *PreSum) Sum(i, j int) int {
    if i <= 0 {
        return ps.preSum[j]
    }
    return ps.preSum[j] - ps.preSum[i-1]
}

func subarraysDivByK(nums []int, k int) int {
    modSum := make(map[int]int)
    modSum[0]=1 // 初始 空串为0
    preSum := &PreSum{}
    preSum.InitPre(nums)
    ans :=0
    for _, pre := range preSum.preSum {
        mod := (pre%k+k)%k // 防止出现负数
        ans += modSum[mod] // 以pre[j]结尾并可被k整除
        modSum[mod]++ // 统计前缀取模个数
    }

    return ans
}
/*
[4,5,0,-2,-3,1]
5
[-1,5]
5
*/

练习4 进制转化可被 5 整除的二进制前缀

题目链接：https://leetcode-cn.com/problems/binary-prefix-divisible-by-5/

题目大意

给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。

返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
示例 2：

输入：[1,1,1]
输出：[false,false,false]
示例 3：

输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
示例 4：

输入：[1,1,1,0,1]
输出：[false,false,false,false,false]

提示：

1 <= A.length <= 30000
A[i] 为 0 或 1

题目解析

从前往后遍历，转化成十进制结果，利用加法，乘法取模公式。

前n位转化成的数字为
$ $x[n] = A[0]*2^{n-1}+A[1]*2^{n-2}+...+A[n-1]*2^0\\ 利用公式1，3可以逐步计算出x[n]%5$ $

AC代码

func prefixesDivBy5(nums []int) []bool {
    ans := make([]bool, len(nums))
    x :=0
    for i, n := range nums {
        x = (x*2+n)%5
        if x==0 {
            ans[i]=true
        }
    }

    return ans
}

练习5 大数取模可被 K 整除的最小整数

题目链接：https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/

题目大意

给定正整数 K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。

返回 N 的长度。如果不存在这样的 N，就返回 -1。

示例 1：

输入：1
输出：1
解释：最小的答案是 N = 1，其长度为 1。
示例 2：

输入：2
输出：-1
解释：不存在可被 2 整除的正整数 N 。
示例 3：

输入：3
输出：3
解释：最小的答案是 N = 111，其长度为 3。

提示：

1 <= K <= 10^5

题目解析

从前往后遍历，转化成十进制结果，利用加法，乘法取模公式。

n位1转化成的数字为
$ $x[n] = 10^{n-1}+10^{n-2}+...+10^0\\ 利用公式1，3可以逐步计算出x[n]%k$ $
实际运算时，x = (x*10+1)%k, 可以看出这个公式的结果是循环的，一旦出现循环，说明没有答案。

复杂度O(k)，抽屉原理，最多运算k次。

AC代码

func smallestRepunitDivByK(k int) int {
    vis := map[int]bool{}
    for x, i :=0, 1; ;i++ {
        x = (x*10+1)%k
        if vis[x]{break}
        if x==0 {return i}
        vis[x]=true
    }
    return -1
}

练习6 方法数求解统计同构子字符串的数目

题目链接：https://leetcode-cn.com/problems/count-number-of-homogenous-substrings/

题目大意

给你一个字符串 s ，返回 s 中同构子字符串的数目。由于答案可能很大，只需返回对 109 + 7 取余后的结果。

同构字符串的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同构子字符串如下所列：
"a" 出现 3 次。
"aa" 出现 1 次。
"b" 出现 2 次。
"bb" 出现 1 次。
"c" 出现 3 次。
"cc" 出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
示例 2：

输入：s = "xy"
输出：2
解释：同构子字符串是 "x" 和 "y" 。
示例 3：

输入：s = "zzzzz"
输出：15

提示：

1 <= s.length <= 10^5
s 由小写字符串组成

题目解析

对于一个长度为n, 同一个字符组成的字符串，则其同构子字符串的数目是n+n-1+n-2+...+2+1。

是一个等差数列，结果是
$ $\frac{(n+1)*n}{2}$ $
遍历原串，打到同一字符组成的子串。然后逐个相加，并取模。

AC代码

const MOD = int(1e9)+7

func countHomogenous(s string) int {
    sum:=0

    for cnt,i :=0,0;i<len(s);i++ {
        if i>0 && s[i]==s[i-1] {
            cnt++
        } else {
            cnt=1
        }

        sum += cnt
        sum %= MOD
    }

    return sum
}

六、总结

主要内容：

取模是一个数学基础运算，它是一个操作工具，就像平时的加减乘除运算一样。运用时与题目本身的思路没有太大的关系。取模的原理虽然很简单，如果不熟练掌握，往往在编写代码时出现越界等情况。
作用
- 两数a,b 相加（相减）取模m。此时a, b比较大，相加会超出int表示范围，m较小。
- 两数a, b 相乘取模m。此时a*b超出int范围，m范围较小。
- 取模查询，枚举出所有取模情况并保存。待查询使用。
- 进制转化，并取模m。一般进制转化完后是一个大数，但是m较小。
- 大数取模m, 类似于作用4，m较小。
- 方法数求解，一般来说题目中出现这么一行字 由于答案可能会很大，方案数需要对 10^9 + 7 取余，总方法数很大，但是取余后小。

笔者水平有限，有写得不对或者解释不清楚的地方还望大家指出，我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目（首先AK F.*ing leetcode），给大家准备了一些题目，供大家练习参考。干他F.*ing (Fighting?)。