РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 3516 Добавить в вариант

Найдите коэффициент при x^m у многочлена

$P левая круглая скобка x правая круглая скобка = левая круглая скобка 1 плюс x правая круглая скобка умножить на левая круглая скобка 2 плюс x в квадрате правая круглая скобка умножить на левая круглая скобка 4 плюс x в степени 4 правая круглая скобка умножить на левая круглая скобка 8 плюс x в степени 8 правая круглая скобка умножить на \ldots умножить на левая круглая скобка 1024 плюс x в степени 1 в степени 0 в квадрате в степени 4 правая круглая скобка .$

Спрятать решение

Решение.

Заметим, что во всех скобках переменные x входят в степенях 2^k, где $k принадлежит левая фигурная скобка 0, 1, \ldots, 10 правая фигурная скобка .$ Следовательно, чтобы образовалось слагаемое x^m нужно во всех скобках взять $x в степени левая круглая скобка 2 в степени левая круглая скобка k правая круглая скобка правая круглая скобка ,$ где k  — ненулевой бит в двоичном разложении m, и число 2^k, если k  — нулевой бит. B итоге для того, чтобы найти коэффициент при x^m нужно найти двоичное одиннадцатиразрядное разложение числа m (возможно с ведущими нулями). Если $b_1, b_2, \ldots, b_l$   — все нулевые биты этого двоичного разложения, то ответом будет являться число $2 в степени левая круглая скобка b_1 правая круглая скобка плюс b_2 плюс \ldots плюс b_l.$

Ответ: $2 в степени левая круглая скобка b_1 правая круглая скобка плюс b_2 плюс \ldots плюс b_l.$

Олимпиада Университета Иннополис Innopolis Open, 9 класс, 1 тур (отборочный) 1 этап, 2017 год

Классификатор: Алгебра: числа. Различные системы счисления

Спрятать решение · Помощь