algorithm - 1a + 2a^2 + 3a^3 + ... + na^n 的 O(log n) 解

Question

任务是找到给定 n 和 a 的方程式之和。所以对于等式 1a + 2a^2 + 3a^3 + ... + na^n，我们可以使用以下公式(来自观察)找到序列中的第 n 个元素:

第 n 个元素 = a^n * (n-(n-2)/n-(n-1)) * (n-(n-3)/n-(n-2)) * ... * (n/(n-1))

我认为将上面的公式修改为求和公式，是不可能简化n个元素求和的。即使可能，我假设它会涉及使用指数n，这将引入n次循环；从而导致解决方案不是 O(log n)。我能得到的最佳解决方案是简单地找到每个元素的比率，即 a(n+1)/n 并将其应用于 n-1 元素以找到第 n 个 元素。

我想我可能遗漏了什么。有人可以为我提供解决方案吗？

Answer 1

您可以使用矩阵求幂来解决这个问题以及许多类似的问题。

让我们从这个序列开始:

A[n] = a + a^2 + a^3 ... + a^n

这个序列可以用一个简单的公式生成:

A[i] = a*(A[i-1] + 1)

现在，如果我们考虑您的顺序:

B[n] = a + 2a^2 + 3a^3 ... + na^n

我们可以使用前一个公式生成:

B[i] = (B[i-1] + A[i-1] + 1) * a

如果我们制作一个包含我们需要的所有组件的向量序列:

V[n] = (B[n], A[n], 1)

然后我们可以构造一个矩阵 M 以便:

V[i] = M*V[i-1]

所以:

V[n] = (M^(n-1))V[1]

由于矩阵的大小固定为 3x3，因此可以使用 exponentiation by squaring在矩阵本身上计算 M^(n-1) 在 O(log n) 时间内，最后的乘法需要常数时间。

这是在 python 中使用 numpy 的实现(因此我不必包含矩阵乘法代码):

import numpy as np

def getSum(a,n):
    # A[n] = a + a^2 + a^3...a^n
    # B[n] = a + 2a^2 + 3a^3 +. .. na^n
    # V[n] = [B[n],A[n],1]

    M = np.matrix([
        [a, a, a],  # B[i] = B[i-1]*a + A[i-1]*a + a
        [0, a, a],  # A[i] = A[i-1]*a + a
        [0, 0, 1]
        ])

    # calculate MsupN = M^(n-1)
    n-=1
    MsupN=np.matrix([[1,0,0],[0,1,0],[0,0,1]]);

    while(n>0):
        if n%2 > 0:
            MsupN *= M
            n-=1
        M*=M
        n=n/2

    # calculate V[n] = MsupN*V
    Vn = MsupN*np.matrix([a,a,1]).T;
    return Vn.item(0,0);