← 返回题目列表

Codeforces · 643/F

F. 熊和果汁

中文机器翻译题面 查看原题

客栈里有n只熊,有p个睡觉的地方。熊会在一起聚会几个晚上(和几天)。

熊喜欢喝果汁。他们不喜欢酒,但无法通过味道或气味将酒与果汁区分开。

熊不喝酒就不睡觉。熊喝完酒后几个小时必须睡觉。聚会结束后很多天他就会醒来。

Radewoosh 是旅馆的老板。他想在熊面前放一些桶。一桶将盛装葡萄酒,所有其他桶将盛装果汁。拉德伍什将挑战熊,寻找装有葡萄酒的桶。

每天晚上,都会按照以下顺序发生以下情况:

1. 每只熊必须选择一组(可能是空的)桶。同一个桶可能会被许多熊选择。
2. 每只熊从他选择的每个桶中喝一杯。
3. 所有喝了酒的熊都会睡觉(正是那些选择了装酒的桶的熊)。他们会在聚会结束很多天后醒来。如果没有足够的地方睡觉,熊就会立即失败。

最后,如果确定酒在哪里并且至少有一只醒着的熊,那么熊获胜(除非他们之前因为睡觉的地方太多而输了)。

Radewoosh 希望让熊获胜。他考虑了 q 个场景。在第 i 个场景中,聚会将持续 i 个晚上。然后,让 Ri 表示如果空头表现最佳,他们肯定会获胜的最大桶数。让我们定义 $$X_{i} = ( i \cdot R_{i} ) \mod 2^{32}$$。你的任务是找到 $${ X _ { 1 } \oplus X _ { 2 } \oplus \ldots \oplus X _ { q } }$$,其中 $$\bigcirc$$ 表示异或(也表示为 XOR)。

请注意,同一个桶可能会被许多熊选择,并且所有熊都会立即入睡。

输入

输入的唯一一行包含三个整数 n、p 和 q (1 ≤ n ≤ 109, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000)——分别是熊的数量、睡觉的地方的数量和场景的数量。

输出

打印一个整数,等于 $${ X _ { 1 } \oplus X _ { 2 } \oplus \ldots \oplus X _ { q } }$$。

示例

输入 #1

5 1 3

输出 #1

32

输入 #2

1 100 4

输出 #2

4

输入 #3

3 2 1

输出 #3

7

输入#4

100 100 100

输出#4

381863924

注意

在第一个样本中,有 5 只熊,只有 1 个睡觉的地方。我们有 R1 = 6,R2 = 11,R3 = 16,所以答案是 $$6 \oplus 22 \oplus 48 = 32$$。我们来分析一下2天场景下的最优策略。有 R2 = 11 个桶,其中 10 个装有果汁。

- 在第一个晚上,第 i 只熊只选择了第 i 个桶。 如果前 5 个桶中的一个盛有酒,那么一只熊就会睡觉。然后,熊获胜,因为它们知道酒在哪里,并且至少有一只醒着的熊。 但假设前 5 个桶中没有一个装有葡萄酒。第二天晚上,第i只熊选择了5 + i的桶。 如果 6 – 10 桶中的一桶装有酒,那么一只熊就会睡觉。在这种情况下,空头再次获胜。 如果没人睡觉,那么酒就在桶里 11.

在第二个样本中,只有一只熊。他应该每天晚上选择一套空桶。否则,他可能会得到酒,而熊会输(因为必须至少有一只醒着的熊)。因此,对于任意天数,Ri = 1。答案是 $$1 \oplus 2 \oplus 3 \oplus 4 = 4$$。