← 返回题目列表

Codeforces · 446/E

E. DZY 爱桥梁

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

DZY 在他家附近拥有 2m 个岛屿,编号从 1 到 2m。他喜欢建造桥梁来连接岛屿。他建造的每一座桥都需要一天的时间才能走完。

DZY 有一个奇怪的搭建桥梁的规则。对于每对岛屿 u, v (u ≠ v),他建造了 2k 座不同的桥梁连接它们,其中 $$k = \max \left\{ k : 2^k | abs(u - v) \right\}$$ (a|b 表示 b 可以被 a 整除)。这些桥是双向的。

此外,DZY 还建造了一些桥梁连接他的家和岛屿。具体来说,从他的家到第 i 个岛有 ai 座不同的桥梁。这些都是单向桥,所以他离开家后就再也不会回来了。

DZY决定去海岛观光。起初他在家。他选择并走过其中一座连接他家的桥梁,到达了某个岛屿。之后,他将在岛上度过 t 天。每天,他可以选择留下来休息,也可以步行过桥去另一个岛。允许在岛上停留一天以上。还允许多次过一座桥。

假设在第 t 天之后 DZY 就站在第 i 个岛。令 ans[i] 为 DZY 在第 t 天后到达第 i 个岛屿的方式数。你的任务是计算每个 i 模 1051131 的 ans[i]。

输入

为了避免巨大的输入,我们使用以下方式生成数组a。给定数组的前 s 个元素:a1, a2, ..., as。所有其他元素应按以下公式计算:ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m)。

第一行包含三个整数 m、t、s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105))。

第二行包含 s 个整数 a1, a2, ..., as (1 ≤ ai ≤ 106)。

输出

为了避免巨大的输出,您只需输出所有 i 模 1051131 (1 ≤ i ≤ 2m) 的所有答案的异或和,即 (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor...异或(ans[n] mod 1051131)。

示例

输入 #1

2 1 4
1 1 1 2

输出 #1

1

输入 #2

3 5 6
389094 705719 547193 653800 947499 17024

输出 #2

556970

注意

在第一个示例中,ans = [6,7,6,6]。

如果他想在一天后回到 1 号岛,他有 6 种不同的方式:

1. 家 —> 1 -(停留)-> 1
2.首页 —> 2 —> 1
3.首页 —> 3 —> 1
4. home —> 3 —> 1(注意1和3之间有两个不同的桥)
5.首页 —> 4 —> 1
6. home —> 4 —> 1(注意从 home 到 4 有两个不同的桥)

在第二个样本中,(a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849), ans = [235771, 712729、433182、745954、139255、935785、620229、644335]。