Да, для сработала регулярность .
Вобщем та формула, что я предлагал, работает только для некоторых .
Для других можно другие формулы подобрать (на основе неприводимых многочленов).
А для других (не связанных со степенью 2) - вообще непонятно. Пробовал подобрать линейную рекурсию - не вышло.
Может там и нет регулярности, просто надо перебором искать.
Московская МО-2020
Московская МО-2020
zykov писал(а):Source of the post Ian писал(а):
Source of the post так как приводим.
Там видимо должен быть многочлен .
Впрочем они оба неприводимые.
Они задают одну и ту же последовательность, только в разные стороны. Одна зеркально симметрична второй.
Если одна из последовательностей имеет максимальную длину, то и вторая тоже.
Московская МО-2020
Тут ещё такая тонкость, что многочлен должен быть не просто неприводимым, а должен быть примитивным многочленом.
Например при будет 3 неприводимых многочлена: , , . Из них только первые два генерируют максимальную последовательность.
Например при будет 3 неприводимых многочлена: , , . Из них только первые два генерируют максимальную последовательность.
Московская МО-2020
Кстати, с ростом длины будет уже больше одного решения.
Так при будет уже 6 примитивных многочленов (3 пары симметричных).
Многочлен даёт вектор
Многочлен даёт вектор
Многочлен даёт вектор
Все три вектора различны - не совмещаются сдвигом/отражением.
Так при будет уже 6 примитивных многочленов (3 пары симметричных).
Многочлен даёт вектор
Код: Выбрать все
1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0
Многочлен даёт вектор
Код: Выбрать все
1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0
Многочлен даёт вектор
Код: Выбрать все
1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0
Все три вектора различны - не совмещаются сдвигом/отражением.
Московская МО-2020
Насчёт случая, когда это не степень двойки,
Попробовал посчитать (это длина вектора 27), так тут вектора с 13 совпадениями не нашлось. Максимум 11 совпадений.
Так что (если там нет ошибки) есть случаи, когда нет решения.
Зато следующий за ним - степень двойки, длина вектора 31 - как мы видели для даёт сразу 3 решения.
zykov писал(а):Source of the post Интересно, что во всех этих случаях () есть только один подходящий вектор
Попробовал посчитать (это длина вектора 27), так тут вектора с 13 совпадениями не нашлось. Максимум 11 совпадений.
Так что (если там нет ошибки) есть случаи, когда нет решения.
Зато следующий за ним - степень двойки, длина вектора 31 - как мы видели для даёт сразу 3 решения.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 19 гостей