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?，不可接受。需要优化。
可以使用倍增算法解决。
$$
通过上式可以把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位转化成的数字为
$$
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 = (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。
是一个等差数列，结果是
$$
遍历原串，打到同一字符组成的子串。然后逐个相加，并取模。
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 加法取模应用 题目链接 https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
- 练习2 取模查询 题目链接 https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/
- 练习3 取模查询 题目链接 https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/
- 练习4 进制转化 题目链接 https://leetcode-cn.com/problems/binary-prefix-divisible-by-5/
- 练习5 大数取模 题目链接 https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/
- 练习6 方法数求解 题目链接 https://leetcode-cn.com/problems/count-number-of-homogenous-substrings/
AK leetcode
leetcode相关题目都在下面了，拿起武器挨个点名呗。
- https://leetcode-cn.com/problems/2vYnGI/
- https://leetcode-cn.com/problems/4xy4Wx/
- https://leetcode-cn.com/problems/5TxKeK/
- https://leetcode-cn.com/problems/Uh984O/
- https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
- https://leetcode-cn.com/problems/check-if-array-is-sorted-and-rotated/
- https://leetcode-cn.com/problems/concatenation-of-consecutive-binary-numbers/
- https://leetcode-cn.com/problems/count-all-possible-routes/
- https://leetcode-cn.com/problems/count-all-valid-pickup-and-delivery-options/
- https://leetcode-cn.com/problems/count-different-palindromic-subsequences/
- https://leetcode-cn.com/problems/count-good-meals/
- https://leetcode-cn.com/problems/count-nice-pairs-in-an-array/
- https://leetcode-cn.com/problems/count-number-of-homogenous-substrings/
- https://leetcode-cn.com/problems/count-ways-to-make-array-with-product/
- https://leetcode-cn.com/problems/create-sorted-array-through-instructions/
- https://leetcode-cn.com/problems/decode-ways-ii/
- https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
- https://leetcode-cn.com/problems/find-all-good-strings/
- https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
- https://leetcode-cn.com/problems/number-of-restricted-paths-from-first-to-last-node/
- https://leetcode-cn.com/problems/number-of-sets-of-k-non-overlapping-line-segments/
- https://leetcode-cn.com/problems/number-of-sub-arrays-with-odd-sum/
- https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/
- https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/
- https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza/
- https://leetcode-cn.com/problems/number-of-ways-to-paint-n-3-grid/
- https://leetcode-cn.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/
- https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
- https://leetcode-cn.com/problems/number-of-ways-to-split-a-string/
- https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/
- https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
- https://leetcode-cn.com/problems/range-sum-of-sorted-subarray-sums/
- https://leetcode-cn.com/problems/rectangle-area-ii/
- https://leetcode-cn.com/problems/restore-the-array/
- https://leetcode-cn.com/problems/sum-of-floored-pairs/
- https://leetcode-cn.com/problems/super-pow/
- https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays/
- https://leetcode-cn.com/problems/binary-prefix-divisible-by-5/
- https://leetcode-cn.com/problems/nth-magical-number/
以上题目太多，大家适当选择就行，下面还有进阶题目。
大神进阶
http://acm.hdu.edu.cn/showproblem.php?pid=5187 乘法应用
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
#字节跳动##学习路径#
交通银行工作强度 39人发布