Блог пользователя sp937

Need help solving "Sum and Xor" problem from ICPC Chennai 2016 regionals
Автор sp937, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить