← 返回题目列表

Codeforces · 1906/K

K. 牌组构建游戏

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

您正在与朋友玩牌组构建游戏。有 $$$N$$$ 卡,编号从 $$$1$$$ 到 $$$N$$$。卡$$$i$$$ 的价值为$$$A_i$$$。

您想要构建两套牌;一份给您,一份给您的朋友。一张牌不能同时存在于两副牌中,并且允许不使用所有$$$N$$$牌。牌组也可以是空的,即不包含任何牌。

一副牌的威力由这副牌中纸牌值的按位异或表示。空牌组的力量是$$$0$$$。

如果两副牌具有相同的威力,则游戏是平衡的。

确定构建两副牌的方法数量,以使游戏保持平衡。如果其中一副牌包含至少一张不同的牌,则两种方式被认为是不同的。由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模计算答案。

输入

第一行由整数 $$$N$$$ ($$$2 \le N \le 100\,000$$$) 组成。

以下行由 $$$N$$$ 整数 $$$A_i$$$ ($$$1 \le A_i \le 100\,000$$$) 组成。

输出

输出一个整数,表示构建两副牌以使游戏平衡的方式数量。输出对 $$$998\,244\,353$$$ 取模的答案。

示例

输入 #1

4
16 12 4 8

输出 #1

9

输入 #2

4
1 2 4 8

输出 #2

1

输入 #3

2
1 1

输出 #3

5

输入#4

6
1 1 1 2 2 2

输出#4

169

注意

示例输入/输出 #1 的说明

将 $$$S$$$ 和 $$$T$$$ 分别表示为你的牌组和你朋友的牌组中的一组牌。有 $$$9$$$ 的方法来构建牌组,以使游戏保持平衡。

- $$$S = \{\}$$$ 和 $$$T = \{\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{2, 3, 4\}$$$ 和 $$$T = \{\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{\}$$$ 和 $$$T = \{2, 3, 4\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{2, 4\}$$$ 和 $$$T = \{3\}$$$。两套牌的威力均为$$$4$$$。
- $$$S = \{3\}$$$ 和 $$$T = \{2, 4\}$$$。两套牌的威力均为$$$4$$$。
- $$$S = \{2, 3\}$$$ 和 $$$T = \{4\}$$$。两套牌的威力均为$$$8$$$。
- $$$S = \{4\}$$$ 和 $$$T = \{2, 3\}$$$。两套牌的威力均为$$$8$$$。
- $$$S = \{3, 4\}$$$ 和 $$$T = \{2\}$$$。两套牌的威力均为$$$12$$$。
- $$$S = \{2\}$$$ 和 $$$T = \{3, 4\}$$$。两套牌的威力均为$$$12$$$。

示例输入/输出#2 的说明

使游戏平衡的唯一方法是将两副牌都清空。

示例输入/输出 #3 的说明

有 $$$5$$$ 的方法来构建牌组以使游戏保持平衡。

- $$$S = \{\}$$$ 和 $$$T = \{\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{1, 2\}$$$ 和 $$$T = \{\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{\}$$$ 和 $$$T = \{1, 2\}$$$。两套牌的威力都是$$$0$$$。
- $$$S = \{1\}$$$ 和 $$$T = \{2\}$$$。两套牌的威力均为$$$1$$$。
- $$$S = \{2\}$$$ 和 $$$T = \{1\}$$$。两套牌的威力均为$$$1$$$。