natsukagami's blog

A question about xor sums
By natsukagami, history, 9 years ago, In English

Hi Codeforces! I was wondering if we could compute a ^ (a + b) ^ (a + 2b) ^ ... ^ (a + kb) in O(1) or such. Thought about it a lot but still I have no solutions :( Do you have any idea? Thank you!

Tags xor
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Simplify the problem to k = 1.
  2. Simplify the problem to a = 1.
  3. Print the first few numbers and look for a pattern.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't quite get the idea. Can you explain it more detailed?

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

      Fine, here you go.

      • There are three parameters: a, b and k. Let us first learn how to solve simpler problems by fixing some of the parameters to some small values.

      • With a = 1, k = 1, solve the problem f (b) = a ^ (a + b) ^ (a + 2b) ^ ... ^ (a + kb). Output the first few values and observe.

      • Once you have the solution for the simpler problem, you can return a and k as parameters. For a, it is just g (a, b) = f (b) - f (a - 1). For k, it is perhaps h (a, b, k) = g (a, b) * k or something similar.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        If a = 1, k = 1 then obviously f(b) = 1 ^ (b + 1), I guess?

        If so then g(a, b) as provided by you is wrong, I suppose.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Ow, sorry, I mixed up the letters b and k. The interesting problem reduction is f (k) for a = 1, b = 1, not f (b) for a = 1, k = 1. Then return a and b into the picture.

          → Reply