Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | numbers.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | numbers.out | |||
Максимальный балл: | 100 |
Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N2 сумм). Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.
Решение, работающее для K≤20 и N≤106, будет набирать не менее 70 баллов.
Числа N,K,P,Q. Последовательность чисел a0,...,aN−1 генерируется так. 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 |
|
|
2 |
|
|
3 |
|
|