Processing math: 50%

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

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

Условие

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

Решение, работающее для K20 и N106, будет набирать не менее 70 баллов.

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

Числа N,K,P,Q. Последовательность чисел a0,...,aN1 генерируется так. a_0 = 1,\,a_{i+1} = (a_i \cdot P + Q) \mod 2^K

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

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

Ограничения

0 \le N \le 10^7;

1 \le K \le 24;

1 \le P,\,Q \le 10^9 + 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.062s 0.009s 13