algorithm - 确定 (x^2 + x + 1)^n 中 x^m 项的系数是偶数还是奇数

Question

对于给定的整数 n 和 m，确定 x^m 项在 (x^2+x +1)^n 是偶数还是奇数？

例如，如果 n=3 且 m=4，(x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1，所以 x^4 项的系数为 6(=偶数)。

n 和m 有10^12那么大，我想在几秒内计算，所以你不能用线性时间计算。

你有什么高效的算法吗？

Answer 1

首先请注意，如果只对 x^m 的系数是奇数还是偶数感兴趣，则可以将多项式的系数视为有限域 F2 的元素。

注意 (1+x+x^2)^2 = (1+x^2+x^4) mod 2 因为交叉项都是偶数。事实上，如果 n 是 2 的幂，则 (1+x+x^2)^n = (1 + x^n + x^2n) mod 2。

对于一般的n，写成2的幂和(即二进制)。

n = (2^a1 + 2^a2 + 2^a3 + ... + 2^ak).

然后将2的各次幂对应的次幂相乘:

(1+x+x^2)^n = (1+x^(2^a1)+x^(2^(a1+1))) * ((1+x^(2^a2)+x^(2^(a2+1))) * ...

此乘积中的每个项现在只有 3 个因子，如果 n 以 10^12 为界，则最多有 35 或 36 个因子。所以很容易将它们相乘。

这是执行此操作的一些 Python 代码:

# poly_times computes the product of polynomials
# p and q over the field F2. They are each
# represented by a set of non-zero coefficients.
# For example set([0, 2, 5]) corresponds to x^0 + x^2 + x^5.
def poly_times(p, q):
    result = set()
    for i in p:
        for j in q:
            if i+j in result:
                result.remove(i+j)
            else:
                result.add(i+j)
    return result

# Return the coefficient of x^m in (1+x+x^2)^n.
def coeff(n, m):
    prod = set([0])
    i = 0
    while n:
        if n % 2:
            prod = poly_times(prod, [0, 2**i, 2**(i+1)])
        i += 1
        n >>= 1
    return 1 if m in prod else 0

for m in xrange(10):
    print m, coeff(3, m)

print coeff(1947248745, 1947248745034)    

优化

对于设置了大量位的 n，当 n 接近 10^12 时，这会变得太慢。

但是，可以通过将多项式幂分成两部分来大大加快速度，然后在最后一步中找到 m 的系数，而不是通过完全多项式乘法，而是通过计算对每个部分的系数总和为 m。这是优化的 coeff:

# poly_times computes the product of polynomials
# p and q over the field F2. They are each
# represented by a set of non-zero coefficients.
# For example set([0, 2, 5]) corresponds to x^0 + x^2 + x^5.
# Coefficients larger than m are discarded.
def poly_times(p, q, m):
    result = set()
    for i in p:
        for j in q:
            if i + j > m:
                continue
            if i+j in result:
                result.remove(i+j)
            else:
                result.add(i+j)
    return result

# Return the coefficient of x^m in (1+x+x^2)^n.
def coeff(n, m):
    if m > 2*n: return 0
    prod = [set([0]), set([0])]
    i = 0
    while n:
        if n % 2:
            prod[i//20] = poly_times(prod[i//20], [0, 2**i, 2**(i+1)], m)
        i += 1
        n >>= 1
    s = 0
    for x in prod[0]:
        s += m-x in prod[1]
    return s % 2

for m in xrange(10):
    print m, coeff(3, m)

print coeff(0xffffffffff, 0xffffffffff)

请注意，这可以在几秒钟内计算出 coeff(0xffffffffff, 0xffffffffff)，并且 0xffffffffff 大于 10**12。