Свойства коэффициентов многочленов, раскрытие скобок и бином Ньютона
Ошибка.
Попробуйте повторить позже
Пусть 
— двоичный вектор длины 8. Обозначим 
— циклический сдвиг вектора 
на 
позиций вправо. Например, если
то 
При этом считаем, что 
Под суммой векторов 
и
будем понимать вектор
Здесь 
— стандартная операция сложения битов: 
Пусть
Найдите 
такие, что при любом исходном векторе 
выполняется равенство
Источники:
Подсказка 1
Пупупу… Какие-то непонятные векторы, с которыми работать не очень понятно как, да и просто непривычно! На что можно заменить любой вектор, чтобы с этим было удобнее работать?
Подсказка 2
Да, можно заменить любой вектор длины a на многочлен, степени одночленов которого — это числа от 0 до a(включительно)! Подумайте, как можно отобразить операцию циклического сдвига на многочлене?
Подсказка 3
Верно, можно просто умножать все его на одночлены на степень, равную величине сдвига и после этого от каждой степени оставлять только остаток по модулю длины вектора! Тогда какому многочлену соответствует вектор x?
Подсказка 4
Да, это многочлен, который состоит из одночленов со степенями 0, 1, 4. А какое условие должно выполняться, чтобы мы нашли многочлен v?
Подсказка 5
Верно, нужно, чтобы произведение многочлена x на многочлен v равнялось единице(учитывая, что можно заменять степени на остаток по модулю введённой степени многочлена)! Осталось найти такой многочлен v, для которого это выполняется!
Заметим, что 
для любого натурального числа 
. Вектору 
взаимно однозначно соответствует
многочлен
Тогда циклический сдвиг вектора 
на 
позиций вправо равносилен умножению многочлена 
на 
и приведению степеней
мономов по модулю 
.
Вектору 
соответствует многочлен 
. Таким образом, нахождение 
таких, что
равносильно нахождению многочлена 
со свойством 
(с учётом приведения степеней
мономов по модулю 
). Найти многочлен 
можно методом неопределённых коэффициентов, но быстрее из следующего
алгоритма:
Следовательно,
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
