sum遇到整数溢出

Question

我的印象是 python 整数是任意精度的。但是今天在解决 a leetCode problem 和多次提交错误答案时，我终于将 mod 添加到我的解决方案中并且它起作用了。我很困惑为什么会这样，下面是我的代码：

import math

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if target>d*f or target<d:
            return 0
        memo = {}
        return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

    # def recurse(self,d,f,target,memo):

    def recurse(self,d,f,target,memo):
        key = "%d %d"%(d,target)
        if key in memo:
            return memo[key]
        if d*f<target or target<d:
            return 0
        elif d==1:
            return 1
        else:
            ways = 0
            for i in range(1,f+1):
                # following line uncommented, and the next one commented, gives correct answer
                #ways = (ways+self.recurse(d-1,f,target-i,memo))%(math.pow(10,9) + 7)
                ways += self.recurse(d-1,f,target-i,memo)

            memo[key] = ways
            return memo[key]

我的猜测是溢出导致了错误的结果，每次求和时修改部分结果解决了这个问题。或者还有什么我想念的吗？

Answer 1

您正在用浮点数计算：

return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

这会强制使用浮点数计算模数，导致您得出错误结果的不是整数溢出而是浮点数不准确。

让我们d, f, target = 30, 30, 500。那么int(self.recurse(d, f, target, memo)returns1319186227454333254490768998141738589030871，一个int而math.pow(10, 9) + 7就是1000000007.0，一个float.

这就是你正在做的事情：

print(1319186227454333254490768998141738589030871 % 1000000007.0)  # wrong
811448245.0

如果您改为确保股息也是整数（10 ** 9 + 7 或 1000000007）：

print(1319186227454333254490768998141738589030871 % 1000000007)  # right   
222616187

sum遇到整数溢出

Integer overflow encountered in sum

python

integer-overflow

python-3.x