Задачи
Числа
Числа
Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N^2 сумм).
Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.
Входные данные
Числа N, K, P, Q (0 ≤ N ≤ 10^7, 1 ≤ K ≤ 24, 1 ≤ P, Q ≤ 10^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