快速多项式移位

我仍然没有完全掌握算法，但是您遇到了一些错误：

1. u开始于n结束的力量0。为了使卷积起作用，您需要将其反转，因为您期望卷积函数中的系数是有序的。
2. v多项式中的系数仅取决于j，而不取决于n-j（您使用i）
3. 仅n+1需要卷积的第一个元素（您不需要n+1...的幂）2n。
4. 产生的卷积（不是真的卷积吗？）是“向后的”，因为您的最终结果将从处开始计算i=0，因此的功效x**(n-i=n)。

将所有这些放在一起：

from math import factorial

def convolve(f, h):
    g = [0] * (len(f) + len(h) - 1)
    for hindex, hval in enumerate(h):
        for findex, fval in enumerate(f):
            g[hindex + findex] += fval * hval
    return g

def shift(f, a):
    n = len(f) - 1
    u = [factorial(i)*c for i, c in enumerate(f)][::-1]
    v = [factorial(n)*a**i//factorial(i) for i in range(n + 1)]
    g = convolve(u, v)
    g = [g[n-i]//(factorial(n)*factorial(i)) for i in range(n+1)][::-1]
    return g

f = [1, 2, 3, -4, 5, 6, -7, 8, 9]
print(shift(f, 1))

我懂了

[9, 80, 301, 636, 840, 720, 396, 132, 23]

我不知道为什么这与您的期望不同，但是我希望这能使您步入正轨。