A question about xor sums

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

Автор natsukagami, история, 11 лет назад, По-английски

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!

xor

natsukagami
11 лет назад
7

Комментарии (7)

Написать комментарий?

Gassa

11 лет назад, скрыть # |

Simplify the problem to k = 1.
Simplify the problem to a = 1.
Print the first few numbers and look for a pattern.

→ Ответить

natsukagami

11 лет назад, скрыть # ^ |

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

→ Ответить

Gassa

11 лет назад, скрыть # ^ |

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.

→ Ответить

natsukagami

11 лет назад, скрыть # ^ |

-8

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.

→ Ответить

Gassa

11 лет назад, скрыть # ^ |

← Rev. 2 →

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.