计算斐波那契时的模数问题

Question

我正在尝试解决一个问题，该问题需要我计算高达 10^18 mod 10^9+7 的斐波那契数。在线法官说我在小案例中得到了正确的答案（不需要模数），但在较大的案例中我得到了错误的答案。否则算法没有问题，但是将结果保存到字典中的记忆化table似乎失败了。我不知道为什么。luku = int(input())table = {0:0, 1:1, 2:1}def fib(num):    if num in table:        return table[num];    if num % 2 == 0:        puoli = num / 2;        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;        table[num] = ans;        return ans;    else:        puoli = (num-1) / 2;        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;        table[num] = ans;        return ans;print(fib(luku))例如，输入 54774730983471038 我得到的是 946469205 而不是正确答案 795317107。

Answer 1

背诵没什么不好。

可能令您惊讶的是，问题在于浮点精度（是的，您的数字被截断了）。

您应该/用整数除法运算符//（双）替换浮动除法运算符（单斜杠）。

以下代码，以及上面提到的唯一修复，对我有用：

luku = int(input())

table = {0:0, 1:1, 2:1}

def fib(num):

    if num in table:

        return table[num];

    if num % 2 == 0:

        puoli = num // 2;

        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;

        table[num] = ans;

        return ans;

    else:

        puoli = (num-1) // 2;

        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;

        table[num] = ans;

        return ans;

print(fib(luku))

看：

ibug@ubuntu:~ $ python3 t.py

54774730983471038

795317107