求根为1至n的多项式系数及组合乘积和的高效算法问询

嘿，这个问题本质上就是计算1到n的k阶初等对称和——也就是你说的“前n个自然数中每次取i个元素的所有组合乘积之和”，刚好有高效的解法能达到你要的接近O(nlogn)的时间复杂度，咱们来详细拆解：

首先要理清：根为1、2、…、n的多项式是 $\prod_{i=1}^n (x - i)$，展开后形如 $x^n - e_1 x^{n-1} + e_2 x^{n-2} - ... + (-1)^n e_n$，其中 $e_k$ 就是你要计算的第k阶组合乘积之和，也就是k阶初等对称和。

这个方法通过分治思想结合快速傅里叶变换（FFT）快速计算多项式乘积，从而一次性得到所有对称和，时间复杂度为 $O(n \log^2 n)$，对于n较大的场景（比如n>1000）比常规的O(n²)递推高效太多。

思路步骤 #

1. 分治拆分：把1到n的序列分成左右两半，比如左半是1到m，右半是m+1到n（取m = n//2）。
2. 递归计算子问题：分别计算左半的生成函数 $L(t) = \prod_{i=1}^m (1 + i t)$ 和右半的生成函数 $R(t) = \prod_{i=m+1}^n (1 + i t)$，这两个多项式的系数就是对应子序列的各阶初等对称和。
3. FFT卷积合并：将L(t)和R(t)做卷积，得到整个序列的生成函数 $P(t) = L(t) * R(t)$，卷积后的系数就是1到n的各阶初等对称和 $e_0, e_1, ..., e_n$（其中e₀=1，对应空乘积）。

简单示例验证 #

比如n=4：

• 左半1-2的生成函数：$(1+1t)(1+2t) = 1 + 3t + 2t²$（对应e₀=1, e₁=3, e₂=2）
• 右半3-4的生成函数：$(1+3t)(1+4t) = 1 + 7t + 12t²$（对应e₀=1, e₁=7, e₂=12）
• 卷积后得到：$1 + 10t + 35t² + 50t³ + 24t⁴$，对应e₁=10（1+2+3+4）、e₂=35（1×2+1×3+1×4+2×3+2×4+3×4）、e₃=50、e₄=24，完全符合要求。

简化代码示例（Python） #

这里用numpy的FFT实现卷积，实际工程中可以用更高效的FFT库或手写分治逻辑：

import numpy as np

def compute_elementary_symmetric_sums(n):
    def divide_conquer(l, r):
        if l == r:
            # 生成多项式 (1 + l*t)
            return np.array([1, l], dtype=np.int64)
        mid = (l + r) // 2
        left = divide_conquer(l, mid)
        right = divide_conquer(mid+1, r)
        # 用FFT做卷积
        len_left, len_right = len(left), len(right)
        fft_len = 1 << (len_left + len_right - 1).bit_length()
        left_fft = np.fft.fft(left, fft_len)
        right_fft = np.fft.fft(right, fft_len)
        result_fft = left_fft * right_fft
        result = np.fft.ifft(result_fft).real.round().astype(np.int64)
        # 截断到有效长度
        return result[:len_left + len_right - 1]
    
    full_poly = divide_conquer(1, n)
    # 返回e₁到eₙ，对应full_poly[1:]
    return full_poly[1:]

# 测试n=4
print(compute_elementary_symmetric_sums(4))  # 输出 [10 35 50 24]

如果是在模质数的场景下（比如算法竞赛），可以用NTT（快速数论变换）替代FFT，避免浮点数精度问题，效率也更高。目前没有已知的O(n)精确计算所有初等对称和的方法，但O(nlog²n)已经足够应对绝大多数实际需求，比O(n²)递推在n较大时快几个数量级。

内容的提问来源于stack exchange，提问作者Deepesh Thakur