algorithm - 存储为字符串的数字的所有子序列的总和

Question

求以字符串模 (10^9)+7 存储的数字的所有子序列之和。该号码最多可以有 N=2*(10^5) 位数字。

例子 - 如果字符串是 123，它的子序列是 1, 2, 3, 12, 23, 13, 123。答案 = 1+2+3+12+23+13+123 = 177。

Answer 1

设T(i)为N的前i位之和，写成N[k] 表示 N 的第 k 位。

然后:

T(0) = 0
T(i) = T(i-1) + T(i-1) * 10 + N[k] * (2**i)

那是因为T(i)的子序列之和是T(i-1)的子序列之和加上T的子序列之和(i-1) 每个都添加了第 k 个数字。有 2**i 个，乘以 10 通勤求和。

简化，将其放入代码中，然后对 k 进行模运算，给出了相对简单(并且在位数上是线性时间)的解决方案:

def subsequences(n, k):
    total = 0
    pow2 = 1
    for i, ds in enumerate(n):
        total = (11 * total + pow2 * int(ds)) % k
        pow2 = (2 * pow2) % k
    return total

print subsequences('123', 10**9 + 7)

输出:

177