C++取模易错点:由于答案可能会很大,请你将结果对1e9+7取模后再返回


在做算法题时我们经常会遇到这样一句话:
由于答案可能会很大,请你将结果对10^9 + 7取模后再返回

附:为什么很多程序竞赛题目都要求答案对 1e9+7 取模?

  1. 1000000007是一个质数
  2. int32位的最大值为2147483647,所以对于int32位来说1000000007足够大
  3. int64位的最大值为2^63-1,对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出

这句话看上去只要对变量取模就可以了,但实际上取模的时机有一定的讲究,比如新手很容易犯一下两个错误

错误1:用max比较很大数据时,先取模

取mod的时候,如果题目要求你算最大值,并且说由于答案可能很大,输出结果请对1e9+7取,那你千万不能在max函数更新最大值时就取模,这样很可能会出错

比如:题目过程中有四个数据

2e9+71e9+61e9+51e9+4

然后算法中你用max求最大值时,如果先模上1e9+7,那你会得到1e9,1e9+6,1e9+5,1e9+4,并且max函数算出的最大值是1e9+6,可是这四个数的最大值应该是2e9 + 7才对

正确做法:在求max的时候不要先取mod,而是都以long long型数据比大小,最后得到最大值是2e9 + 7,再对它取mod,得到结果是1e9 + 7

例题:1339. 分裂二叉树的最大乘积

错误代码示例

class Solution {
public:
    // 乘积 = 某个节点下所有子节点的和 *(整个树的和 - 某个节点下所有子节点的和)
    typedef long long LL;
    LL rmax = 0;
    LL Total = 0;
    static const LL mod = 1e9 + 7;

    // 遍历每个结点,更新最大值
    LL TreeSum(TreeNode* root) {
        if (!root) return 0;
        LL left = TreeSum(root->left);
        LL right = TreeSum(root->right);
        LL subsum = left + right + root->val;

        // 此处先取模,所以数据很大时会出错
        rmax = max(rmax, (Total - subsum) * subsum % mod);
        return subsum;
    }

    int maxProduct(TreeNode* root) {
        if (!root) return 0;
        Total = TreeSum(root);
        rmax = 0;

        TreeSum(root);
        return rmax % mod;
    }
};

![](https://img-blog.csdnimg.cn/20200211175718956.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI3NTk1,size_16,color_FFFFFF,t_70#pic_left =70%x70%)
类似题:5752. 子数组最小乘积的最大值

错误2:直到return时才取模

如果让你算1+2+…+n的值(由于答案可能很大,输出结果请对1e9+7取)
n的取值范围是1 ~ $10^{10000}$

那显然如果你在中间过程中不先取mod,必然会爆数据范围,因为不管是int还是long long甚至是double(最大约$10^{308}$)都无法存下这个数据

...
long long res = 0;
for(int i = 1; i <= n ; i ++) {
    res = res + i; // n巨大,res无法存下这个数据
}

return res % (1e9 + 7);

正确做法:在算res的过程中取模

...
long long res = 0;
for(int i = 1; i <= n ; i ++) {
    res = (res + i) % (1e9 + 7); // n巨大,res无法存下这个数据
}
return res;

有的人会说这不是与错误1矛盾了吗,其实完全不矛盾

  • 错误1是在比较多个很大的数据(不超过long long)
  • 错误2是在维护1个很大的数据,那你先取模和后取模,就没有区别了,因为结果都是一样的

另外有的时候我们经常喜欢用 += 之类的符号,但容易犯以下错误

long long res = 0;
for(int i = 1; i <= n ; i ++) {
    res += i % (1e9 + 7); // n巨大,res无法存下这个数据
}
return res;

上面的代码实际上并没有对res进行取模,而只是对$i$进行取模,当res累加很多数后,是会超过long long,从而出现报错的。所以你要么在下面加一行res %= (1e9 + 7),要么用res = (res + i) % (1e9 + 7);


现在看面试题:剪绳子II这个题,就知道为什么不能用动态规划了,因为取余之后max函数就不能用来比大小

数据较小时下面代码是可以过的,数据大了就不行了,因为不能在max出取模

class Solution {
public:
    // f(n) = max(f(i) * f(n - i)) i:1,..,n-1
    int cutRope(int number) {
        // number = 1,2,3时剪一刀,值会变小,所以特殊考虑这几种情况
        if(number < 2) return 0;
        if (number == 2) return 1;
        if (number == 3) return 2;

        int *f = new int[number + 1];
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;

        // f(n) n大于3时,表示切若干刀后的最大值
        for (int i = 4; i <= number; i ++) {
            int rmax = number;
            for (int j = 1; j <= i / 2; j ++) {
                rmax = max(rmax, f[j] * f[i - j]);
            }
            f[i] = rmax;
        }

        int res = f[number];
        delete[] f;

        return res;
    }
};

错误3:是否真的取模了?

下面的式子取模过程有个坑点:

$a[i][j]$并没有取模就直接与$pre[i][j]$相乘了(*%是从左往右算的)

res = res % mod + pre[i][j] % mod * a[i][j] % mod;

正确的写法:

res = res % mod + pre[i][j] % mod * (a[i][j] % mod);

Author: SHWEI
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source SHWEI !
评论
 Previous
详解git clone --depth=1的用法 详解git clone --depth=1的用法
前言 本文以GitHub仓库 https://github.com/labuladong/fucking-algorithm 为例,详细介绍git clone --depth=1的用法 情况一:git clonegit clone htt
2020-09-04
Next 
GitHub中Pull Request的具体过程详解 GitHub中Pull Request的具体过程详解
Pull Request 简单明了的解释“有一个仓库,叫Repo A。你如果要往里贡献代码,首先要Fork这个Repo,于是在你的Github账号下有了一个Repo A2,。然后你在这个A2下工作,Commit,push等。然后你希望原始仓
2020-07-24
  TOC