eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Числа

Числа

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N^2 сумм).

Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.

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

Числа N, K, P, Q (0N10^7, 1K24, 1P, Q10^9+7, P и Q - простые). Последовательность чисел a_0, ...,a_{N-1} генерируется так. a_0 = 1, a_{i+1} = (a_i·P+Q) mod 2^K.

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

В первой строке выведите K+1 целое число - количества единичек в разрядах (Можно было бы вывести остальные количества, не только первые K+1. Но они нули.) Первым выводить нужно ответ для младшего разряда.

Пример

Входные данные #1
3 10 3 5
Выходные данные #1
4 4 4 5 4 3 0 0 0 0 0
Автор Сергей Копелиович