这是一个创建于 1931 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天做题，遇到大整数累加遇到 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 操作才是对的呢？有没有什么范式之类的？
谢谢大家！
 |
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 因为没有最终取模。 多个数累加，最后一步取模是必须的，如果你担心中间结果溢出，还可以在每一次加完都取模一次。 |
Select Language