Темы --> Информатика --> Другое
    Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(21 задач)
    Формула(17 задач)
    Комбинаторика(9 задач)
---> 54 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 5 6 7 8 9 10 11 Отображать по:
#113938
Уравнения математической магии
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько существует неотрицательных решений данного уравнения. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные

Вам предстоит решить задачу для нескольких возможных значений параметра \(a\). В первой строке находится целое число \(t\) (\(1 \le t \le 1000\)) — количество этих значений.

В последующих \(t\) строках находятся значения параметра \(a\), каждое значение — целое число от \(0\) до \(2^{30} - 1\) включительно.

Выходные данные

Для каждого значения параметра \(a\) выведите строке одно целое число — количество неотрицательных решений уравнения с данным значением параметра. Ответы выводите в том же порядке, в каком параметры следуют во входных данных.

Можно доказать, что количество решений всегда конечно.

Примечание

Определим операцию побитового исключительного ИЛИ (XOR).

Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\).

Пусть \(r = x \oplus y\) — результат операции XOR над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:

\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)

Для первого значения параметра только \(x = 0\) является решением уравнения.

Для второго значения параметра решениями уравнения являются \(x = 0\) и \(x = 2\).

Примеры
Входные данные
3
0
2
1073741823
Выходные данные
1
2
1073741824
#113939
Уравнения математической магии
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю \(2^{32}\). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю \(2^{32}\), Кристобаля Хунту интересует количество таких решений \(x\), что \(0 \leq x < 2^{32}\). Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные

В первой строке задано одно целое число \(a\) (\(0 \leq a \leq 2^{32} - 1\)).

Выходные данные

Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание

Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\). Пусть \(r = x \oplus y\) — результат операции XOR над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:

\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)

В первом примере решениями уравнения являются \(0\) и \(2147483648 = 2^{31}\), так как \(0 - (0 \oplus 0) - 0 = 0 - 0 - 0 = 0\) и \(0 - (0 \oplus 2147483648) - 2147483648 = -4294967296 = -2^{32} = 0\) по модулю \(2^{32}\).

Во втором примере решениями уравнения являются \(0\), \(2\), \(2147483648 = 2^{31}\) и \(2147483650 = 2^{31} + 2\).

В третьем примере решениями являются все \(x\), для которых выполнено \(0 \leq x < 2^{32}\).

Примеры
Входные данные
0
Выходные данные
2
Входные данные
2
Выходные данные
4
Входные данные
4294967295
Выходные данные
4294967296
#113998
Число множеств с разделенными элементами
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вам даны два числа n и k . Назовем подмножество A множества {1, ..., n } хорошим, если любые два различные элемента A различаются не менее, чем на k . Найдите количество хороших множеств максимальной мощности. Так как ответ может быть достаточно большим, выведите его по модулю 10 9 + 7 .

Входные данные

В первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 10 5 .

В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 10 5 и 1 ≤ k ≤ 10 9 .

Выходные данные

Для каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 10 9 + 7 .

Система оценки

Подзадача 1 (30 баллов): \(T = 1, n \le 20, k \le 20\).

Подзадача 2 (15 баллов): \(k \le 2\).

Подзадача 3 (55 баллов): нет доп. ограничений.

Примеры
Входные данные
4
10 4
10 1
10 10
4 3
Выходные данные
4
1
10
1
#114004
Много смайликов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

«Опять эти задачи про смайлики!» – грустил Серёжа на олимпиаде. Действительно, на этот раз авторы дали бесконечное число задач, пронумерованных натуральными числами \((1, 2, 3, \dots)\), и все они были про смайлики. Серёжа много тренировался перед олимпиадой, и выбрал себе лучшую тактику: после задачи с номером \(x\) он решает задачу с номером \(x\) xor \((x/2)\), где xor – это побитовое исключающее или, а деление производится с округлением вниз. Например, \(4\) xor \(8\) равно \(12\), \(7\) xor \(11\) тоже равно \(12\), \(5\) xor \((5/2)\) равно \(7\).

Серёжа считает задачу с номером \(x\) хорошей, если он решит \(k\) задач (начиная с \(x\), выбирая их по своей тактике, при этом, возможно он решит некоторые задачи не по одному разу), а (\(k + 1\))-й задачей опять окажется \(x\). Помогите Серёже – для данного \(k\) найдите количество хороших задач. Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).

Входные данные

В единственной строке дано целое число k , 1 ≤ k ≤ 10 9 .

Выходные данные

Выведите одно целое число – количество хороших задач по модулю 10 9 + 7 . Если хороших задач бесконечное количество, выведите - 1 .

Группы тестов

Тесты 3-15 \(-\) 30 баллов. \(n \le 10000\).
Тесты 16-35 \(-\) 70 баллов. Дополнительных ограничений нет.
Примеры
Входные данные
2
Выходные данные
3
Входные данные
260
Выходные данные
15
Страница: << 5 6 7 8 9 10 11 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест