ivplay's blog

Need Idea of a problem(ChengDu regional 2007/2008)
By ivplay, 11 years ago, In English
  • 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?
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply