Определяющий коэффициент для x ^ m члена в (x ^ 2 + x + 1) ^ n четный или нечетный

Ответ 1

Да, линейное время в количестве бит на входе.

Рассматриваемые коэффициенты представляют собой триномиальные коэффициенты T(n, m). Для биномиальных коэффициентов мы использовали бы теорему Лукаса; пусть выработать трехмерный аналог для p = 2.

Работая mod 2 и следуя доказательству Натана Фана,

(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) of 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

Ответ 2

Примечание (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 фактора и не более 35 или 36 из них, если n ограничено 10 ^ 12. Поэтому легко их размножать.

Вот код 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.

Ответ 3

Коэффициент интереса зависит от количества путей, из которых n можно выбрать из x² + x + 1, так что сумма степеней выбранных членов равна m. Эти способы могут быть сгруппированы в группы, которые имеют одинаковое количество выбранных x²-терминов и x-терминов (из этого выбирается количество раз 1).

Пусть a - число членов x², b - число x членов, c - число 1 членов в определенной группе.

Тогда справедливы следующие равенства:

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

Очевидно, что обычно существует несколько групп с разными значениями для a, b, c. Как только a определено, также определяются значения для b и c. Таким образом, нужно только перебирать возможные значения для а, чтобы получить все группы.

Если вы должны были написать алгоритм грубой силы, чтобы получить сам коэффициент, в 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) вернет количество способов, чтобы взять k элементов из n элементов, т.е. биномиальный коэффициент.

Произведение двух вызовов combi отвечает на следующий вопрос:

Сколько способов взять время x² и b раз в x? Обратите внимание, что количество способов, с помощью которых можно использовать постоянный член, равно 1, когда были сделаны другие 2 варианта.

Теперь, поскольку нам нужно только знать, является ли конечный коэффициент нечетным или четным, нам также нужно знать, является ли биномиальный коэффициент нечетным или четным. Как описано в 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.

Ответ 4

Хорошо, я просто подумал о решении. Здесь:

• Вспомните уравнение как написанное n раз, (a.x^2 + b.x^1 + c).(a.x^2 + b.x^1 + c)...n раз. a, b и c - константы, которые я предполагал в целом.
• Теперь нам нужно выбрать член из каждого, так что результат умножения всех таких членов приведет к x ^ m
• Теперь я могу сказать, что нам нужно найти решения уравнения t1.2 + t2 = m, где t1 не имеет значения x^2 и t2 of 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 x 2, и b не выбрано из x. Решениями этого уравнения являются {0, 3} и {1, 1}. Теперь, поскольку мы должны также учитывать порядок, в котором мы их выбираем, мы применим комбинаторика на следующем шаге.

• Коэффициент будет равен 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}

• Это добавляет до 63, которые вы можете проверить, вручную умножив, и вы получите 63.

Надеюсь, я поняла.