A14583 | Array Elimination
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given array $a_1, a_2, \ldots, a_n$ , consisting of non-negative integers.
Let's define operation of "elimination" with integer parameter $k$ ( $1 \leq k \leq n$ ) as follows:
- Choose $k$ distinct array indices $1 \leq i_1 < i_2 < \ldots < i_k \le n$ .
- Calculate $x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$ , where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) (notes section contains formal definition).
- Subtract $x$ from each of $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ ; all other elements remain untouched.
Find all possible values of $k$ , such that it's possible to make all elements of array $a$ equal to $0$ using a finite number of elimination operations with parameter $k$ . It can be proven that exists at least one possible $k$ for any array $a$ .
Note that you firstly choose $k$ and only after that perform elimination operations with value $k$ you've chosen initially.
Let's define operation of "elimination" with integer parameter $k$ ( $1 \leq k \leq n$ ) as follows:
- Choose $k$ distinct array indices $1 \leq i_1 < i_2 < \ldots < i_k \le n$ .
- Calculate $x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$ , where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) (notes section contains formal definition).
- Subtract $x$ from each of $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ ; all other elements remain untouched.
Find all possible values of $k$ , such that it's possible to make all elements of array $a$ equal to $0$ using a finite number of elimination operations with parameter $k$ . It can be proven that exists at least one possible $k$ for any array $a$ .
Note that you firstly choose $k$ and only after that perform elimination operations with value $k$ you've chosen initially.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 10^4$ ). Description of the test cases follows.
The first line of each test case contains one integer $n$ ( $1 \leq n \leq 200\,000$ ) — the length of array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i < 2^{30}$ ) — array $a$ itself.
It's guaranteed that the sum of $n$ over all test cases doesn't exceed $200\,000$ .
The first line of each test case contains one integer $n$ ( $1 \leq n \leq 200\,000$ ) — the length of array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i < 2^{30}$ ) — array $a$ itself.
It's guaranteed that the sum of $n$ over all test cases doesn't exceed $200\,000$ .
输出格式
For each test case, print all values $k$ , such that it's possible to make all elements of $a$ equal to $0$ in a finite number of elimination operations with the given parameter $k$ .
Print them in increasing order.
Print them in increasing order.
输入输出样例
输入 #1
5 4 4 4 4 4 4 13 7 25 19 6 3 5 3 1 7 1 1 1 5 0 0 0 0 0
输出 #1
1 2 4 1 2 1 1 1 2 3 4 5
In the first test case:
- If $k = 1$ , we can make four elimination operations with sets of indices $\{1\}$ , $\{2\}$ , $\{3\}$ , $\{4\}$ . Since $\&$ of one element is equal to the element itself, then for each operation $x = a_i$ , so $a_i - x = a_i - a_i = 0$ .
- If $k = 2$ , we can make two elimination operations with, for example, sets of indices $\{1, 3\}$ and $\{2, 4\}$ : $x = a_1 ~ \& ~ a_3$ $=$ $a_2 ~ \& ~ a_4$ $=$ $4 ~ \& ~ 4 = 4$ . For both operations $x = 4$ , so after the first operation $a_1 - x = 0$ and $a_3 - x = 0$ , and after the second operation — $a_2 - x = 0$ and $a_4 - x = 0$ .
- If $k = 3$ , it's impossible to make all $a_i$ equal to $0$ . After performing the first operation, we'll get three elements equal to $0$ and one equal to $4$ . After that, all elimination operations won't change anything, since at least one chosen element will always be equal to $0$ .
- If $k = 4$ , we can make one operation with set $\{1, 2, 3, 4\}$ , because $x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4$ $= 4$ .
In the second test case, if $k = 2$ then we can make the following elimination operations:
- Operation with indices $\{1, 3\}$ : $x = a_1 ~ \& ~ a_3$ $=$ $13 ~ \& ~ 25 = 9$ . $a_1 - x = 13 - 9 = 4$ and $a_3 - x = 25 - 9 = 16$ . Array $a$ will become equal to $[4, 7, 16, 19]$ .
- Operation with indices $\{3, 4\}$ : $x = a_3 ~ \& ~ a_4$ $=$ $16 ~ \& ~ 19 = 16$ . $a_3 - x = 16 - 16 = 0$ and $a_4 - x = 19 - 16 = 3$ . Array $a$ will become equal to $[4, 7, 0, 3]$ .
- Operation with indices $\{2, 4\}$ : $x = a_2 ~ \& ~ a_4$ $=$ $7 ~ \& ~ 3 = 3$ . $a_2 - x = 7 - 3 = 4$ and $a_4 - x = 3 - 3 = 0$ . Array $a$ will become equal to $[4, 4, 0, 0]$ .
- Operation with indices $\{1, 2\}$ : $x = a_1 ~ \& ~ a_2$ $=$ $4 ~ \& ~ 4 = 4$ . $a_1 - x = 4 - 4 = 0$ and $a_2 - x = 4 - 4 = 0$ . Array $a$ will become equal to $[0, 0, 0, 0]$ .
Formal definition of bitwise AND:
Let's define bitwise AND ( $\&$ ) as follows. Suppose we have two non-negative integers $x$ and $y$ , let's look at their binary representations (possibly, with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$ . Here, $x_i$ is the $i$ -th bit of number $x$ , and $y_i$ is the $i$ -th bit of number $y$ . Let $r = x ~ \& ~ y$ is a result of operation $\&$ on number $x$ and $y$ . Then binary representation of $r$ will be $r_k \dots r_2 r_1 r_0$ , where:
$$$$ r_i = \begin{cases} 1, ~ \text{if} ~ x_i = 1 ~ \text{and} ~ y_i = 1 \\ 0, ~ \text{if} ~ x_i = 0 ~ \text{or} ~ y_i = 0 \end{cases} $$$$
- If $k = 1$ , we can make four elimination operations with sets of indices $\{1\}$ , $\{2\}$ , $\{3\}$ , $\{4\}$ . Since $\&$ of one element is equal to the element itself, then for each operation $x = a_i$ , so $a_i - x = a_i - a_i = 0$ .
- If $k = 2$ , we can make two elimination operations with, for example, sets of indices $\{1, 3\}$ and $\{2, 4\}$ : $x = a_1 ~ \& ~ a_3$ $=$ $a_2 ~ \& ~ a_4$ $=$ $4 ~ \& ~ 4 = 4$ . For both operations $x = 4$ , so after the first operation $a_1 - x = 0$ and $a_3 - x = 0$ , and after the second operation — $a_2 - x = 0$ and $a_4 - x = 0$ .
- If $k = 3$ , it's impossible to make all $a_i$ equal to $0$ . After performing the first operation, we'll get three elements equal to $0$ and one equal to $4$ . After that, all elimination operations won't change anything, since at least one chosen element will always be equal to $0$ .
- If $k = 4$ , we can make one operation with set $\{1, 2, 3, 4\}$ , because $x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4$ $= 4$ .
In the second test case, if $k = 2$ then we can make the following elimination operations:
- Operation with indices $\{1, 3\}$ : $x = a_1 ~ \& ~ a_3$ $=$ $13 ~ \& ~ 25 = 9$ . $a_1 - x = 13 - 9 = 4$ and $a_3 - x = 25 - 9 = 16$ . Array $a$ will become equal to $[4, 7, 16, 19]$ .
- Operation with indices $\{3, 4\}$ : $x = a_3 ~ \& ~ a_4$ $=$ $16 ~ \& ~ 19 = 16$ . $a_3 - x = 16 - 16 = 0$ and $a_4 - x = 19 - 16 = 3$ . Array $a$ will become equal to $[4, 7, 0, 3]$ .
- Operation with indices $\{2, 4\}$ : $x = a_2 ~ \& ~ a_4$ $=$ $7 ~ \& ~ 3 = 3$ . $a_2 - x = 7 - 3 = 4$ and $a_4 - x = 3 - 3 = 0$ . Array $a$ will become equal to $[4, 4, 0, 0]$ .
- Operation with indices $\{1, 2\}$ : $x = a_1 ~ \& ~ a_2$ $=$ $4 ~ \& ~ 4 = 4$ . $a_1 - x = 4 - 4 = 0$ and $a_2 - x = 4 - 4 = 0$ . Array $a$ will become equal to $[0, 0, 0, 0]$ .
Formal definition of bitwise AND:
Let's define bitwise AND ( $\&$ ) as follows. Suppose we have two non-negative integers $x$ and $y$ , let's look at their binary representations (possibly, with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$ . Here, $x_i$ is the $i$ -th bit of number $x$ , and $y_i$ is the $i$ -th bit of number $y$ . Let $r = x ~ \& ~ y$ is a result of operation $\&$ on number $x$ and $y$ . Then binary representation of $r$ will be $r_k \dots r_2 r_1 r_0$ , where:
$$$$ r_i = \begin{cases} 1, ~ \text{if} ~ x_i = 1 ~ \text{and} ~ y_i = 1 \\ 0, ~ \text{if} ~ x_i = 0 ~ \text{or} ~ y_i = 0 \end{cases} $$$$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted