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

LightningBilly · 2021 年6 月 14 日 13:31

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

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

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

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

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

二、公式证明

公式 1

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

证明：

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

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

(a%m+b%m)%m = ((q1*m+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 = q1*m+r1, b=q2*m+r2, q1, q2, r1, r2为整数, 且 0<=r1,r2<m。

则(a*b)%m = ((q1*m+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 = ((q1*m+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

多数情况下，2*m 一般是小于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 加法取模应用斐波那契数列

题目链接力扣

题目大意

写一个函数，输入 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 取模查询可被三整除的最大和

题目链接：力扣

题目大意

给你一个整数数组 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 整除的子数组

题目链接：力扣

题目大意

给定一个整数数组 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 整除的二进制前缀

题目链接：力扣

题目大意

给定由若干 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 整除的最小整数

题目链接：力扣

题目大意

给定正整数 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 方法数求解统计同构子字符串的数目

题目链接：力扣

题目大意

给你一个字符串 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?)。

七、实战训练

代码基础训练题

光说不练假把式，学完了怎么也要实操一下吧，快快动用把刚才那几题A了。

练习1 加法取模应用题目链接力扣
练习2 取模查询题目链接力扣
练习3 取模查询题目链接力扣
练习4 进制转化题目链接力扣
练习5 大数取模题目链接力扣
练习6 方法数求解题目链接力扣

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
https://leetcode-cn.com/problems/nth-magical-number/

以上题目太多，大家适当选择就行，下面还有进阶题目。

大神进阶

http://acm.hdu.edu.cn/showproblem.php?pid=5187 乘法应用

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

在这里插入图片描述

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

一、简介

二、公式证明

公式 1

公式2

公式3

三、作用

四、注意事项及优化

加（减）法取模

乘法取模

五、牛刀小试

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

题目大意

题目解析

AC代码

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

题目大意

题目解析

AC代码

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

题目大意

题目解析

AC代码

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

题目大意

题目解析

AC代码

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

题目大意

题目解析

AC代码

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

题目大意

题目解析

AC代码

六、总结

七、实战训练

代码基础训练题

AK leetcode

大神进阶

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

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

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

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

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

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