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

Question

对于给定的整数n和m，确定x^m项 in的系数(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和m10^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。

Answer 2

是的，输入中位数的线性时间。

所讨论的系数是三项式系数T(n, m)。对于二项式系数，我们将使用卢卡斯定理；让我们算出 的三项式模拟p = 2。

工作mod 2并遵循 Nathan Fine 的证明，

(1 + x + x^2)^{2^i} = 1 + x^{2^i} + x^{2^{2 i}}

(1 + x + x^2)^n
    = prod_i ((1 + x + x^2)^{2^i n_i})
        where n = sum_i n_i 2^i and n_i in {0, 1} for all i
        (i.e., n_i is the binary representation of n
    = prod_i (1 + x^{2^i n_i} + x^{2^i 2 n_i})
    = prod_i sum_{m_i = 0}^{2 n_i} x^{2^i}
    = sum_{(m_i)} prod_i x^{2^i m_i}
        taken over sequences (m_i) where 0 ≤ m_i ≤ 2 n_i.

在二项式情况下，下一步是观察，对于 的系数x^m，最多有一个选择(m_i)其x^{2^i m_i}因子具有正确乘积，即 的二进制表示m。

在三项式情况下，我们必须考虑伪比特可以是零、一或二(m_i)的二进制伪表示。当且仅当对于所有这样的情况，我们都有m对总和的贡献。in_i = 0m_i = 0

我们可以编写一个逐位扫描n的自动机。m状态a是初始的和接受的。

a (0:0:nm') -> a nm'    [emit 0]
a (1:0:nm') -> a nm'    [emit 0]
            -> b nm'    [emit 2]
a (1:1:nm') -> a nm'    [emit 1]

b (0:1:nm') -> a nm'    [emit 0]
b (1:0:nm') -> b nm'    [emit 1]
b (1:1:nm') -> a nm'    [emit 0]
            -> b nm'    [emit 2]

我们可以使用动态规划来计算路径。代码形式：

def trinomial_mod_two(n, m):
    a, b = 1, 0
    while m:
        n1, n = n & 1, n >> 1
        m1, m = m & 1, m >> 1
        if n1:
            if m1:
                a, b = a ^ b, b
            else:
                a, b = a, a ^ b
        elif m1:
            a, b = b, 0
        else:
            a, b = a, 0
    return a

用于咯咯笑的无分支版本：

def trinomial_mod_two_branchless(n, m):
    a, b = 1, 0
    while m:
        n1, n = n & 1, n >> 1
        m1, m = m & 1, m >> 1
        a, b = ((n1 | ~m1) & a) ^ (m1 & b), ((n1 & ~m1) & a) ^ (n1 & b)
    return a

Answer 3

感兴趣的系数取决于可以从x² + x + 1中选择n项的方式数量，因此所选项的幂之和为m。这些方式可以分组到具有相同数量的选定x²项和x项的组中（从中选择1的次数）。

令a为x²项的数量，b为x项的数量，c为特定组中1项的数量。

那么以下等式成立：

       2a + b = m
       a + b + c = n

显然，通常有几个组具有不同的a、b、c值。一旦确定了 a ，也就确定了b和c的值。因此，只需迭代a的可能值即可获得所有组。

如果你要编写一个蛮力算法来获取系数本身，它在 Python 中看起来像这样：

def combi(n, k): # number of ways to take k elements from n elements
    import math
    f = math.factorial
    return f(n) // f(k) // f(n-k)    

def get_coeff(n, m):
    if m > n * 2 or n < 0 or m < 0: # basic argument check
        return None
    if m > n: # mirrored situation is the same
        m = 2*n - m            
    coeff = 0
    for a in range(0, m//2+1):
        b = m - 2*a
        coeff += combi(n, a) * combi(n-a, b)
    return coeff

该函数combi(n, k)将返回从 n 个元素中获取 k 个元素的方法数，即二项式系数。

两次调用combi的乘积回答了以下问题：

我有多少种方法可以乘以x²项和b乘以x项？请注意，一旦做出其他 2 个选择，可以采用常数项的方式数为 1。

现在，既然我们只需要知道最终的系数是奇数还是偶数，我们也只需要知道二项式系数是奇数还是偶数。正如math.stackexchange.com上所解释的，这可以通过一个简单的位操作来确定：

def combi_parity(n, k):
    return (k & (n-k)) == 0

def get_coeff_parity(n, m):
    if m > n * 2 or n < 0 or m < 0: # basic argument check
        return None
    if m > n:
        m = 2*n - m # mirrored situation is the same
    coeff_odd = 0
    for a in range(0, m//2+1):
        b = m - 2*a
        # A product is odd only when both factors are odd (so we perform an "and")
        # A sum changes parity whenever the added term is odd (so we perform a "xor")
        coeff_odd ^= combi_parity(n, a) and combi_parity(n-a, b) 
    return coeff_odd

看到它在repl.it上运行。

Answer 4

好吧，我只是想到了一个解决方案。开始：

1. 把方程想象成写了 n 次，(a.x^2 + b.x^1 + c).(a.x^2 + b.x^1 + c)...n次。a、b 和 c 是我通常假设的常数。
2. 现在，我们必须从每个项中选择一个项，以便所有这些项的乘法结果为 x^m
3. 我现在可以说，我们必须找到方程的解，t1.2 + t2 = m其中t1没有 和x^2的t2出现x。这是因为t1and t2then 会使项的形式为k.x^m（k 是常数）。这是找到这个方程的积分丢番图解，即找到所有令人满意的对{t1, t2}
4. 现在，我们必须在这里应用一些置换来找到系数。假设您有{1, 2}上一步的解决方案之一，那么对于这个 diad，系数将是(1^1.nC1).(2^2.(n-1)C2)系数成分之一。如果将与所有丢番图解相对应的所有此类系数项相加，您将得到系数。

以算法方式实现上述算法对我来说需要一些时间，所以我已经发布了这些步骤。

注意：我搜索了一下，丢番图解决方案有多种算法。这是与此相关的一篇文章：如何在编程中求解线性丢番图方程？

编辑：作为一个例子，

1. 可以说，我们有方程，(x^2 + x^1 + x^1)^3我们必须找到 的系数x^3。因此，我们有m = 3.

2. 单独写方程是为了直观地看到步骤。这是，

   (x^2 + x^1 + x^1).(x^2 + x^1 + x^1).(x^2 + x^1 + x^1)

3. 现在，我们想{x^2, x^1, 1}从这些中选择一个。将有几种方法可以选择它来进行形式的乘法，x^3

4. 为了解决这个问题，我们可以写出等式，2.a + b = 3其中 a 是 x^2 被选中的次数，b 是 x 被选中的次数。这个方程的解是{0, 3}和{1, 1}。现在，因为我们还必须考虑选择它们的顺序，所以我们将在下一步中应用组合学。

5. 系数为，2^0.3C0.3^3.3C3 + 2^1.3C1.3^1.2C1。现在在这里，在第一项中2^0.3C0.3^3.3C3，3C0表示选择 0次出现x^2，3C3意味着 3 次出现 x，这将给出x^3，但我们也乘以，2^0因为 2 是x^2等式中的系数，同样，3^3因为 3 是 x 的系数。同样，您将进行第二项对应于{1, 1}

6. 这加起来是 63，您可以通过手动相乘来验证，您将得到 63。

希望我清楚。