sp937's blog

Need help solving "Sum and Xor" problem from ICPC Chennai 2016 regionals
By sp937, history, 5 years ago, In English

https://www.codechef.com/problems/CHN16H

My observations:

f(2s, 2x) = f(s, x) if

f(2s, 2x) = 3f(s - 1, x) if

f(2s + 1, 2x + 1) = 3f(s, x) if

f(2s + 1, 2x + 1) = f(s - 1, x) if

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not see the question. Going by your recurrence. This recurrence can be calculated in poly logarithmic time if you do it naively.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is easy to compute f(a,b) for some a, b in logarithmic time but the problem is to compute sum f(ia, ib) for all i <= n. a,b <= 30, n <= 10^12.

    → Reply