A16458 | Deck-Building Game
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are playing a deck-building game with your friend. There are $N$ cards, numbered from $1$ to $N$ . Card $i$ has the value of $A_i$ .
You want to build two decks; one for you and one for your friend. A card cannot be inside both decks, and it is allowed to not use all $N$ cards. It is also allowed for a deck to be empty, i.e. does not contain any cards.
The power of a deck is represented as the bitwise XOR of the value of the cards in the deck. The power of an empty deck is $0$ .
The game is balanced if both decks have the same power.
Determine the number of ways to build two decks such that the game is balanced. Two ways are considered different if one of the decks contains at least one different card. Since the answer can be very large, calculate the answer modulo $998\,244\,353$ .
You want to build two decks; one for you and one for your friend. A card cannot be inside both decks, and it is allowed to not use all $N$ cards. It is also allowed for a deck to be empty, i.e. does not contain any cards.
The power of a deck is represented as the bitwise XOR of the value of the cards in the deck. The power of an empty deck is $0$ .
The game is balanced if both decks have the same power.
Determine the number of ways to build two decks such that the game is balanced. Two ways are considered different if one of the decks contains at least one different card. Since the answer can be very large, calculate the answer modulo $998\,244\,353$ .
输入格式
The first line consists of an integer $N$ ( $2 \le N \le 100\,000$ ).
The following line consists of $N$ integers $A_i$ ( $1 \le A_i \le 100\,000$ ).
The following line consists of $N$ integers $A_i$ ( $1 \le A_i \le 100\,000$ ).
输出格式
Output an integer representing the number of ways to build two decks such that the game is balanced. Output the answer modulo $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
Explanation for the sample input/output #1
Denote $S$ and $T$ as the set of cards in your deck and your friend's deck, respectively. There are $9$ ways to build the decks such that the game is balanced.
- $S = \{\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{2, 3, 4\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{\}$ and $T = \{2, 3, 4\}$ . Both decks have the power of $0$ .
- $S = \{2, 4\}$ and $T = \{3\}$ . Both decks have the power of $4$ .
- $S = \{3\}$ and $T = \{2, 4\}$ . Both decks have the power of $4$ .
- $S = \{2, 3\}$ and $T = \{4\}$ . Both decks have the power of $8$ .
- $S = \{4\}$ and $T = \{2, 3\}$ . Both decks have the power of $8$ .
- $S = \{3, 4\}$ and $T = \{2\}$ . Both decks have the power of $12$ .
- $S = \{2\}$ and $T = \{3, 4\}$ . Both decks have the power of $12$ .
Explanation for the sample input/output #2
The only way to make the game balanced is to have both decks empty.
Explanation for the sample input/output #3
There are $5$ ways to build the decks such that the game is balanced.
- $S = \{\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{1, 2\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{\}$ and $T = \{1, 2\}$ . Both decks have the power of $0$ .
- $S = \{1\}$ and $T = \{2\}$ . Both decks have the power of $1$ .
- $S = \{2\}$ and $T = \{1\}$ . Both decks have the power of $1$ .
Denote $S$ and $T$ as the set of cards in your deck and your friend's deck, respectively. There are $9$ ways to build the decks such that the game is balanced.
- $S = \{\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{2, 3, 4\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{\}$ and $T = \{2, 3, 4\}$ . Both decks have the power of $0$ .
- $S = \{2, 4\}$ and $T = \{3\}$ . Both decks have the power of $4$ .
- $S = \{3\}$ and $T = \{2, 4\}$ . Both decks have the power of $4$ .
- $S = \{2, 3\}$ and $T = \{4\}$ . Both decks have the power of $8$ .
- $S = \{4\}$ and $T = \{2, 3\}$ . Both decks have the power of $8$ .
- $S = \{3, 4\}$ and $T = \{2\}$ . Both decks have the power of $12$ .
- $S = \{2\}$ and $T = \{3, 4\}$ . Both decks have the power of $12$ .
Explanation for the sample input/output #2
The only way to make the game balanced is to have both decks empty.
Explanation for the sample input/output #3
There are $5$ ways to build the decks such that the game is balanced.
- $S = \{\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{1, 2\}$ and $T = \{\}$ . Both decks have the power of $0$ .
- $S = \{\}$ and $T = \{1, 2\}$ . Both decks have the power of $0$ .
- $S = \{1\}$ and $T = \{2\}$ . Both decks have the power of $1$ .
- $S = \{2\}$ and $T = \{1\}$ . Both decks have the power of $1$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted