VK Cup 2016 - Раунд 3 |
---|
Закончено |
В гостинице поселились n медведей, но там есть только p спальных мест. Медведи планируют закатить большую вечеринку на несколько ночей (и дней).
Медведи любят пить сок. Они не любят вино, но не могут отличить его от сока ни по вкусу, ни по запаху.
Медведь ложится спать, только если он выпил вина, при этом он уходит спать через несколько часов после этого. Он проснётся только спустя много дней, когда вечеринка уже будет окончена.
Хозяин гостиницы Радевуш хочет предложить медведям несколько бочек с напитками. При этом ровно одна бочка будет содержать вино, а в остальных будет содержаться сок. После этого Радевуш предложит медведям определить, в какой бочке находится вино.
Каждую ночь происходит следующее (ровно в таком порядке):
В конце вечеринки, если однозначно можно определить, в какой бочке находится вино, и хотя бы один медведь не спит, то медведи выигрывают (если, конечно, они не проиграли раньше, потому что кому-то не хватило спальных мест).
Радевуш хотел бы, чтобы медведи выиграли. Он рассматривает q сценариев игры. В i-м сценарии вечеринка продолжается i ночей. Далее пусть Ri обозначает максимальное количество бочек, для которого медведи точно смогут выиграть, если будут действовать оптимально. Обозначим . Вам требуется вычислить , где означает побитовое исключающее или (также известное как XOR).
Обратите внимание, что одна и та же бочка может быть выбрана несколькими медведями и все они одновременно пойдут спать, если она содержит вино.
В единственной строке входных данных записаны три целых числа n, p и q (1 ≤ n ≤ 109, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000) — количество медведей, количество спальных мест и количество сценариев соответственно.
Выведите единственное целое число, равное .
5 1 3
32
1 100 4
4
3 2 1
7
100 100 100
381863924
В первом примере в гостинице находятся 5 медведей и есть только 1 спальное место. Имеем R1 = 6, R2 = 11, R3 = 16, так что ответ равен . Проанализируем стратегию для сценария с 2 днями. Всего есть R2 = 11 бочек, и 10 из них содержат сок.
Во втором примере есть только один медведь. Он не может ничего пить (то есть он выбирает пустое множество бочек каждую ночь), потому что если он уйдёт спать, то медведи сразу проигрывают. Таким образом, для любого числа дней Ri = 1 и ответ равен .
Название |
---|