### ivplay's blog

By ivplay, 10 years ago,
• 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?
• 0

 » 10 years ago, # | ← Rev. 3 →   +1 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.