n 和 m，确定在 (x^2+x+1)^n 中 x^m 项的系数是偶数还是奇数？(x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1，因此 x^4 项的系数为 6（=偶数）。n 和 m 可以达到 10^12，我希望在几秒钟内计算出结果，因此无法使用线性时间计算。首先需要注意，如果一个人只关心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。是的，输入位数的时间复杂度是线性的。
所涉及的系数是三项式系数 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，其中伪比特可以是零、一或两个。当且仅当对于所有 i，使得 n_i = 0，我们有 m_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
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个元素的方式数量，即二项式系数。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上运行它。
a（在我的代码中称为k）仅在满足 combi_parity(n, a) 为True的数字上进行步进。 - Paul Hankin(a.x^2 + b.x^1 + c).(a.x^2 + b.x^1 + c)...n。这里的 a、b 和 c 是常数。t1.2 + t2 = m 的解，其中 t1 表示 x^2 的出现次数，t2表示x的出现次数。这是因为此时 t1 和 t2 会将该项变为形如 k.x^m（k 为常数）。这相当于找到该方程的整数丢番图解，即找到所有满足 {t1, t2} 的解。{1,2}，那么对于这个二元组，系数将为 (1^1.nC1).(2^2.(n-1)C2)，这将成为系数的一个组成部分。如果你将所有与丢番图解对应的系数项相加，就能得到系数。以上算法的实现需要一些时间，所以我只发布了步骤。
注意：我进行了一些搜索，并发现有各种各样的丢番图解算法。以下是一个相关的帖子：如何在编程中解决线性丢番图方程？
编辑：由于要求提供一个示例，
(x^2 + x^1 + x^1)^3，我们要找到 x^3 的系数。因此，我们有 m = 3。将方程式分开写是为了更好地看到步骤。因此，它是：
(x^2 + x^1 + x^1).(x^2 + x^1 + x^1).(x^2 + x^1 + x^1)
现在，我们想从每个方程式中选取 {x^2，x^1，1} 中的任意一个。有多种选择方法，使得它们相乘的形式为 x^3。
为了解决这个问题，我们可以写出方程式 2.a + b = 3，其中a表示选取x^2的次数，b表示选取x的次数。这个方程式的解是，{0, 3} 和 {1, 1}。由于我们还要考虑选取它们的顺序，所以下一步我们将应用组合数学。
系数将是 2^0.3C0.3^3.3C3 + 2^1.3C1.3^1.2C1。现在，在第一项中，2^0 是方程式中 x^2 的系数，3C0 意味着选取 0 个 x^2 和 3C3 意味着选取 3 个 x，这将给出 x^3，但我们还要乘以 2^0，因为 2 是方程式中 x^2 的系数，类似地，乘以 3^3，因为 3 是 x 的系数。类似地，你可以按照与 {1, 1} 相应的第二项处理。
这加起来是 63，你可以手动计算并验证您会得到 63。
希望我表述清楚。
sum(c(n, k)c(n-k, m-2k) for k=0..m/2)。通过对2取模来计算，注意到只有当a&b==b时c(a, b)=1 mod 2（因此您只需要迭代具有子集位的k，这些位是n的位）。但是当n和m很大时，我无法使C版本运行得足够快。如果您想尝试我的代码：https://gist.github.com/paulhankin/5f5aa05231ce8659b6b040d849fd800e - Paul Hankin