CF662A Gambling Nim

如你所知，“Nim”游戏是使用 $n$ 堆石子来进行的，第 $i$ 堆一开始有 $a_i$ 个石子。两位玩家轮流操作。每位玩家可以在自己的回合任选一堆非空石子堆，从中取走任意正整数个石子。不能进行操作的一方判负。 Petya 和 Vasya 玩腻了 Nim 游戏，于是他们发明了自己的版本，称为“赌博 Nim”。他们有 $n$ 张双面牌，第 $i$ 张牌的一面写着数字 $a_i$，另一面写着数字 $b_i$。游戏开始时，两人把所有牌放到桌子上，每张牌随机独立选定正反面朝上。于是获得了一个序列 $c_1, c_2, \ldots, c_n$，其中 $c_i$ 等于 $a_i$ 或 $b_i$。随后用这些牌上数字作为初始堆，拿出 $n$ 堆石子，第 $i$ 堆有 $c_i$ 个石子，继续进行 Nim 游戏，Petya 先手。 假设双方都采取最优策略，求 Petya 获胜的概率。请将答案输出为不可约分数。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$）——牌的数量。 接下来的 $n$ 行，每行包含一张牌的信息，即两个整数 $a_i$ 和 $b_i$（$0 \leq a_i, b_i \leq 10^{18}$）。

输出 Petya 获胜的概率，表示为不可约分数 $p/q$。如果 Petya 获胜的概率为 $0$，请输出 $0/1$。

由 ChatGPT 5 翻译