- https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2014
- Short Description:
- You are given a sequence of N integers (each within the range [0, 2^16 — 1] ) along with P operations and in order to solve this problem you need to process the operations instructed as follows.
There are two kinds of operations that you will be instructed to perform:

- 1) Modification Given a non-negative number T , you need to increase the value of every number in the sequence by T . If the value of any number in the sequence is larger than 2^16 — 1 after the operation, you should divide its value by 2^16 and take the remainder as its value;
- 2) Query Given a non-negative number T , query how many numbers in the sequence satisfies the condition that its bitwise and result with 2^T is greater than zero.
- For simplicity, all you need to do here is to output the sum ( sum < 10, 000, 000, 000 ) of the answers to all queries.
- Can anybody give me some idea to think this problem?

Misunderstood...

EDIT : For each T <= 15, you can maintain D[T][x] = how many numbers are there which is modulo (2^(T+1) — 1) they are equal to x.(This means last T bits). Then if x >= 2^T then it has a bit on 2^T so it means bitwise and is greater then zero.