Python中的子序列和递归

Question

上周末，我在HackerRank上做广告无限挑战赛。在

一个问题是计算一个有限序列的所有子序列的和，如果每个子序列被认为是一个整数。在

例如，序列4,5,6会给出答案4+5+6+45+46+56+456=618。在

我找到了一个递归，并编写了下面的Python代码。它解决了5/13个测试用例。在

剩下的8/13个测试用例有运行时错误。在

我希望有人能发现代码中效率低下的地方，以及如何加快速度。或者，帮我决定递归不是最好的策略。在

# Input is a list, representing the given sequence, e.g. L = [4,5,6]

def T(L): 
    limit = 10**9 + 7  # answer is returned modulo 10**9 + 7
    N = len(L)
    if N == 1: 
        return L[0]
    else:
        last = L[-1] 
        K = L[:N-1]
        ans =  T(K)%limit + 10*T(K)%limit + (last%limit)*pow(2,N-1,limit)
        return ans%limit

Answer 1

这是我对同一个问题（玛纳萨和子序列）的意见。 https://www.hackerrank.com/contests/infinitum-may14/challenges/manasa-and-sub-sequences

我希望这能帮助你想出更好的办法。在

ans = 0
count = 0
for item in raw_input():
    temp = (ans * 10 + (count + 1)*(int(item)))%1000000007
    ans = (ans + temp)%1000000007
    count = (count*2 + 1)%1000000007

print ans