生成函数平移

What · 是什么

生成函数平移（shift）是多项式/幂级数的高级操作，两大主题：① 多项式平移 f(x)↦f(x+c)：已知 f(x) 的系数求 f(x+c) 的系数，有分治法 O(n log² n)、Taylor 公式法（用 f^{(t)}(c) 表达 [x^t]f(x+c)=f^{(t)}(c)/t!）、二项式定理法（三种殊途同归，均归约为卷积 A_0(x)B_0(x) 其中 A_0[i]=f_{n−i}(n−i)!、B_0[i]=c^i/i!）。② 连续点值平移：已知 f(0),f(1),…,f(n)（连续点值）求 f(c),f(c+1),…,f(c+n)，用 Lagrange 插值公式法 O(n log n)（构造 A_0[i]=f(i)(−1)^{n−i}/(i!(n−i)!)、B_0[i]=1/(c−n+i)，[x^{n+t}](A_0B_0) 还原 f(c+t)）。典型应用：同一行第一类无符号斯特林数（上升幂 x^{\overline n} 的平移）、模素数阶乘 n!、二项式系数前缀和、调和数、整式递推等。

Why · 为什么

How · 实现

伪代码

# 多项式平移 f(x+c) mod x^n (Taylor/二项式定理法, 卷积归约)
# 输入 f[0..n-1], 常数 c; 输出 g[0..n-1] = f(x+c)
# A[i] = f[n-1-i]*(n-1-i)!   (i=0..n-1)
# B[i] = c^i / i!            (i=0..n-1)
# C = A * B (卷积) -> C[n-1-k] = k! * g[k]  =>  g[k] = C[n-1-k] / k!

# 连续点值平移 f(c),f(c+1),...,f(c+n): (c>n)
# A[i] = f(i)*(-1)^{n-i}/(i!*(n-i)!)
# B[i] = 1/(c-n+i)
# D = A * B; f(c+t) = D[n+t] * (c+t)! / ((c+t-n-1)!)

Python 实现

MOD = 998244353


def _precompute_factorials(n, mod=MOD):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
    inv = [1] * (n + 1)
    inv[n] = pow(fact[n], mod - 2, mod)
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % mod
    return fact, inv


def _conv(a, b, mod=MOD):
    c = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            c[i + j] = (c[i + j] + x * y) % mod
    return c


def poly_shift(f, c, mod=MOD):
    """多项式平移 f(x+c) 的前 len(f) 项. O(n^2) 朴素卷积(演示)."""
    n = len(f)
    fact, invf = _precompute_factorials(n, mod)
    A = [f[n - 1 - i] * fact[n - 1 - i] % mod for i in range(n)]
    powc = [1] * n
    for i in range(1, n):
        powc[i] = powc[i - 1] * c % mod
    B = [powc[i] * invf[i] % mod for i in range(n)]
    C = _conv(A, B)
    g = [0] * n
    for k in range(n):
        g[k] = C[n - 1 - k] * invf[k] % mod
    return g


def shift_verify(f, c):
    """直接展开验证 (x+c)^k."""
    from math import comb
    g = [0] * len(f)
    for k, fk in enumerate(f):
        for i in range(k + 1):
            g[i] += fk * comb(k, i) * (c ** (k - i))
    return [v % MOD for v in g]


def point_shift(f_points, c, mod=MOD):
    """连续点值平移: 已知 f(0..n), 求 f(c..c+n). c > n 版本. O(n^2) 朴素."""
    n = len(f_points) - 1
    fact, invf = _precompute_factorials(c + n, mod)
    A = []
    for i in range(n + 1):
        A.append(f_points[i] % mod * (1 if (n - i) % 2 == 0 else mod - 1) % mod
                 * invf[i] % mod * invf[n - i] % mod)
    # B[i] = 1/(c-n+i), i=0..2n
    B = [0] * (2 * n + 1)
    for i in range(2 * n + 1):
        denom = (c - n + i) % mod
        B[i] = pow(denom, mod - 2, mod)
    D = _conv(A, B)
    out = []
    for t in range(n + 1):
        val = D[n + t]
        # val = (c+t)! / ((c+t-n-1)!) * f(c+t)
        val = val * fact[c + t] % mod * invf[c + t - n - 1] % mod
        out.append(val)
    return out


def _eval_shift_poly(f, c):
    """对多项式 f(系数) 在点 x 求值."""
    val = 0
    for i in range(len(f) - 1, -1, -1):
        val = val * c + f[i]
    return val


if __name__ == "__main__":
    # 多项式平移: f = 1 + 2x + x^2, c = 1 => (x+1)^2 + 2(x+1) + 1 = x^2+4x+4
    f = [1, 2, 1]
    g = poly_shift(f, 1)
    assert g == [4, 4, 1], g
    assert g == shift_verify(f, 1)
    # 随机验证: f(x)=3x^3+2x+5, c=2
    f2 = [5, 2, 0, 3]
    g2 = poly_shift(f2, 2)
    assert g2 == shift_verify(f2, 2)
    # 连续点值平移: 取 f(x)=x^2, 点值 0,1,4; 平移 c=4 => f(4..6)=16,25,36
    pts = [_eval_shift_poly([0, 0, 1], i) for i in range(3)]  # 0,1,4
    moved = point_shift(pts, 4)
    assert moved == [16, 25, 36], moved
    print("generating-function-shift: all tests passed")

易错点

• 卷积下标错位：A 是逆序 f，C[n-1-k]=k!·g[k] 的索引关系写错
• 连续点值平移分母 c-n+i 为零未处理
• 阶乘预计算范围不足（需到 c+t）
• c 为负/模数时 (c-n+i) 的模处理
• 只验证 f(x+c) 而忘 f 本身有常数项时的符号

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/poly/shift/
• oiwiki-raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/poly/shift.md
• oiwiki-comp-rev✓ https://oi-wiki.org/math/poly/comp-rev/