Задача D. Числа

Автор:Жюри летних сборов 2009   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:256 Мб
Выходной файл:numbers.out  
Максимальный балл:100  

Условие

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

Решение, работающее для K ≤ 20 и N ≤ 106, будет набирать не менее 70 баллов.

Формат входного файла

Числа N, K, P, Q. Последовательность чисел a0, ... , aN − 1 генерируется так. a0 = 1, ai + 1 = (ai ⋅ P + Qmod 2K

Формат выходного файла

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

Ограничения

0 ≤ N ≤ 107;

1 ≤ K ≤ 24;

1 ≤ P, Q ≤ 109 + 7;

P и Q — простые;

Примеры тестов

Входной файл (numbers.in) Выходной файл (numbers.out)
1
3 10 3 5
4 4 4 5 4 3 0 0 0 0 0
2
10 3 3 5
50 25 48 16
3
100 10 17 239
5000 5000 5002 5002 4998 5014 4989 5029 4985 5015 4188

0.099s 0.011s 13