O（log n）求解1a + 2a ^ 2 + 3a ^ 3 + ... + na ^ n

Question

任务是找到给定的方程n和的总和a。因此对于等式1a + 2a^2 + 3a^3 + ... + na^n，我们可以使用以下公式（从观察值中）找到序列中的第n个元素：

n-th element = a^n * (n-(n-2)/n-(n-1)) * (n-(n-3)/n-(n-2)) * ... * (n/(n-1))

我认为通过将上述公式修改为sum公式来简化n个元素的总和是不可能的。即使有可能，我也假设它将涉及使用exponent n，这将引入一个n时间循环。因此导致解不是O（log n）。我能得到的最佳解决方案就是简单地找到每个元素的比率a(n+1)/n，即将其应用于n-1元素以找到n-th元素。

我认为我可能会缺少一些东西。有人可以为我提供解决方案吗？

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，因此可以对矩阵本身进行平方运算来使用幂运算，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);