Numbers#5251
Given non-negative integers, we are interested in examining their pairwise sums, resulting in a total of N^2 sums.
For each binary digit position from to , determine how many times the digit one appears in that position across all these sums.
You are given the integers , , , and (0 \leq N \leq 10^7, 1 \leq K \leq 24, 1 \leq P, Q \leq 10^9+7, and both and are prime numbers). The sequence of numbers a_0, \ldots, a_{N-1} is generated as follows: a_0 = 1, and for each subsequent number, a_{i+1} = (a_i \cdot P + Q) \bmod 2^K.
On the first line, output K+1 integers, representing the counts of ones in each binary digit position, starting with the least significant digit. It is only necessary to output the counts for the first K+1 positions, since the remaining positions contain only zeros.
Example 1