今天做题,遇到大整数累加遇到 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 因为没有最终取模。 多个数累加,最后一步取模是必须的,如果你担心中间结果溢出,还可以在每一次加完都取模一次。 |