解决"没有连续数字的子集数"时的OverFlowError

Question

我正在尝试使用Python解决TalentBuddy中的问题

问题是 :

给定数字N.打印到标准输出可以使用{1,2..N}集合形成的子集总数,但确保没有子集包含任何两个连续的整数.最终计数可能非常大,这就是您必须打印结果模524287的原因.

我已经完成了代码.除了测试6之外,所有测试都没问题.OverFlowError当测试10000000作为我的函数的参数提交时,我得到了.我不知道该怎么做才能解决这个错误

我的代码:

import math
def count_subsets(n):
    step1 = (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** (n + 2))
    step2 = (1 / math.sqrt(5)) * (((1 - math.sqrt(5)) / 2) ** (n + 2))
    res = step1 - step2
    print int(res) % 524287

我想这会占用大量内存.在我在互联网上找到相同主题的数学公式后,我写了这个.
我想我的代码根本不是Pythonic.

如何做到这一点,"Pythonic"方式？怎么解决OverFlowError？

编辑:在问题中,我给出了示例输入3,结果(输出)是5.

说明:5套是,{}, {1}, {2}, {3}, {1,3}.

但是,在测试6中,我给出的问题是:

测试#6的摘要

输入测试:

[10000000]

预期产量:

165366

你的输出:

Traceback (most recent call last):
  On line 4, in function count_subsets:
    step1 = (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** (n + 2))
OverflowError: 

Answer 1

设f(N)为不包含连续数的子集数.有F(N-2)子集包含N和F(N-1)子集,不包含N.这给出:

F(N) = F(N-1) + F(N-2).

F(0) = 1 (there's 1 subset of {}, namely {}).
F(1) = 2 (there's 2 subsets of {1}, namely {} and {1}).

这是斐波那契序列,尽管具有非标准的起始条件.

正如您所发现的那样,使用黄金比率来计算这个公式.问题是对于大N,在浮点计算中需要越来越精确.

进行计算的一种确切方法是使用迭代:

a_0 = 1
b_0 = 2
a_{n+1} = b_n
b_{n+1} = a_n + b_n

这个天真的版本很容易但很慢.

def subsets(n, modulo):
    a, b = 1, 2
    for _ in xrange(n):
        a, b = b, (a + b) % modulo
    return a

相反,标准技巧是将重复的重复应用写为矩阵幂:

( a_n ) = | 0 1 |^N  ( 1 )
( b_n ) = | 1 1 |  . ( 2 )

您可以通过重复平方来计算矩阵功率(使用模数-524287算术).通过平方看直线指数.这是完整的代码:

def mul2x2(a, b, modulo):
    result = [[0, 0], [0, 0]]
    for i in xrange(2):
        for j in xrange(2):
            for k in xrange(2):
                result[i][j] += a[i][k] * b[k][j]
                result[i][j] %= modulo
    return result

def pow(m, n, modulo):
    result = [[1, 0], [0, 1]]
    while n:
        if n % 2: result = mul2x2(result, m, modulo)
        m = mul2x2(m, m, modulo)
        n //= 2
    return result

def subsets(n):
    m = pow([[0, 1], [1, 1]], n, 524287)
    return (m[0][0] + 2 * m[0][1]) % 524287

for i in xrange(1, 10):
    print i, subsets(i)
for i in xrange(1, 20):
    print i, subsets(10 ** i)

这可以为10到10 ^ 19的每个功率打印解决方案,并且它实际上是即时的(我的笔记本电脑上的真实值为0.041秒).