Автор: | Жюри летних сборов 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 + Q) mod 2K
В первой строке выведите K + 1 целое число — количества единичек в разрядах (Можно было бы вывести остальные количества, не только первые K + 1. Но они нули.) Первым выводить нужно ответ для младшего разряда.
0 ≤ N ≤ 107;
1 ≤ K ≤ 24;
1 ≤ P, Q ≤ 109 + 7;
P и Q — простые;
№ | Входной файл (numbers.in ) |
Выходной файл (numbers.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|