V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
AslanFong
V2EX  ›  问与答

关于 modulo 操作的问题

  •  
  •   AslanFong · 2019-08-11 12:52:35 +08:00 · 704 次点击
    这是一个创建于 1920 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天做题,遇到大整数累加遇到 modulo 的问题,想请教一下大家,题目说 Return the number of possible ways modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

    我尝试了两种方案:

    m = (int)1e9 + 7;
    //1
    for(int n = 1; n <= f && n <= j; n++) {
        	dp[i][j] += dp[i - 1][j - n] % m;
        }
    //2
    for(int n = 1; n <= f && n <= j; n++) {
        	dp[i][j] += dp[i - 1][j - n];
            dp[i][j] %= m;
        }
    

    第一种的结果是错的,第二种的结果是对的。实在是不懂,modulo 操作的顺序会怎么改变数值呢?对于多个数累加,到底要在哪一步 modulo 操作才是对的呢?有没有什么范式之类的?

    谢谢大家!

    2 条回复    2019-08-11 14:10:49 +08:00
    lcdtyph
        1
    lcdtyph  
       2019-08-11 13:42:29 +08:00   ❤️ 1
    因为两种写法不等价
    第一种相当于 dp[i][j] = (dp[i][j] + (dp[i-1][j-n] % m))
    第二种相当于 dp[i][j] = ((dp[i][j] + d[i-1][j-n]) % m)
    看到区别了吗,第二种模了最后的结果,第一步只模了其中一个加数。

    举个例子,假设 dp[i][j] == 1e9+6, dp[i-1][j-n] == 8
    那么第一种写法算出来的 dp[i][j] == 1e9 + 14 因为没有最终取模。

    多个数累加,最后一步取模是必须的,如果你担心中间结果溢出,还可以在每一次加完都取模一次。
    AslanFong
        2
    AslanFong  
    OP
       2019-08-11 14:10:49 +08:00
    @lcdtyph 十分感谢!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1036 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 20:17 · PVG 04:17 · LAX 12:17 · JFK 15:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.