Codeforces Round 1120 (Div 2) - C1. Floor of MEX (Easy Version)

C1. Floor of MEX (Easy Version)

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

This is the easy version of the problem. The difference between the versions is that in this version, you only need to find one subset that satisfies the constraints. You can hack only if you solved all versions of this problem.

Let

f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right),

where $S$ is a set of non-negative integers and $x$ is a positive integer. $^{\text{∗}}$

Farmer John chooses a (possibly empty) subset $A\subseteq \{0,1,\ldots,n-1\}$ . He then constructs an array $a$ of length $n$ , where $a_k = f(A,k)$ for every $1\le k\le n$ .

Bessie, being a mischievous cow, hides the set $A$ . Farmer John is left only with the array $a_1,a_2,\ldots,a_n$ .

Your task is to construct any (possibly empty) subset $B\subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$ . Farmer John will only give you arrays where such a $B$ exists.

$^{\text{∗}}\operatorname{mex}(c)$ denotes the minimum excluded (MEX) $^{\text{∗}}$ of the collection $c$ . (in this case, the minimum non-negative integer not present in the set)

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 10^5$ ).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $0 \leq a_i \leq n$ ).

You will only be given arrays where there exists $B \subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ .

Output

For each test case, output two lines.

On the first line, output an integer $m$ — the size of the set $B$ .

On the second line, output $m$ distinct integers $b_1,b_2,\ldots,b_m$ — the elements of $B$ . If $m=0$ , the second line should be empty.

The elements of $B$ may be printed in any order.

If there are multiple solutions, you may output any of them.

Example

Input

3
6
0 3 2 2 2 1
5
2 1 1 1 1
6
1 2 1 1 1 1

Output

Note

For the first test case, one possible answer is

B=\{1,2,3,4,5\}.

Then

f(B,1)=\text{mex}(\{1,2,3,4,5\})=0,

f(B,2)=\text{mex}(\{0,1,2\})=3,

and

f(B,3)=f(B,4)=f(B,5)=2.

Finally,

f(B,6)=\text{mex}(\{0\})=1.

Thus the array is $[0,3,2,2,2,1]$ .

For the second test case, one possible answer is

B=\{0,1\}.

Then $f(B,1)=2$ , and for every $2\le k\le 5$ , we have

\left\{\left\lfloor y/k\right\rfloor : y\in B\right\}=\{0\},

so $f(B,k)=1$ . Therefore, the array is $[2,1,1,1,1]$ .

这是一道非常精妙但结论极其优美的构造题。

题解

1. 问题分析与 $\text{mex}$ 性质

根据题意，对于每个 $k \in \{1, 2, \dots, n\}$ ，均有：

a_k = \text{mex}\left(\left\{\left\lfloor \frac{y}{k}\right\rfloor : y\in B\right\}\right)

由 $\text{mex}$ （最小未出现的非负整数）的定义，上述条件等价于以下两点：

必须包含：对每一个整数 $v \in \{0, 1, \dots, a_k - 1\}$ ，集合 $B$ 中至少存在一个元素 $y$ 使得 $\lfloor y/k \rfloor = v$ 。
绝对不能包含：集合 $B$ 中不能存在任何元素 $y$ 使得 $\lfloor y/k \rfloor = a_k$ 。

2. 禁选区间

从条件 2 出发，满足 $\lfloor y/k \rfloor = a_k$ 的整数 $y$ 满足：

k \cdot a_k \le y \le k \cdot a_k + k - 1

这意味着对于每个 $k$ ，区间 $[k \cdot a_k, k \cdot a_k + k - 1] \cap [0, n - 1]$ 中的所有元素都不能放入集合 $B$ 中。

我们记所有这些被禁止的元素的并集为 $F$ ：

F = \bigcup_{k=1}^n \Big([k \cdot a_k, k \cdot a_k + k - 1] \cap [0, n - 1]\Big)

任何合法的集合 $B$ 都必然满足 $B \subseteq \{0, 1, \dots, n-1\} \setminus F$ 。

3. 贪心构造：选取最大可能集合

题目保证至少存在一个合法的解 $A \subseteq \{0, 1, \dots, n-1\}$ 。
由于 $A$ 是合法的， $A$ 也必须避开所有禁止的区间，因此必有：

A \subseteq \{0, 1, \dots, n-1\} \setminus F

此时，我们直接构造集合 $B$ 为所有未被禁止的元素的全集：

B = \{0, 1, \dots, n-1\} \setminus F

显然有 $A \subseteq B$ 。我们来验证这样的 $B$ 是否对所有 $k$ 都成立：

上界限制： $B$ 中没有任何元素来自禁选集合 $F$ ，因此对任意 $y \in B$ ，都有 $\lfloor y/k \rfloor \neq a_k$ ，即 $a_k \notin \{\lfloor y/k \rfloor : y \in B\}$ 。
下界覆盖：因为 $A \subseteq B$ ，所以： $\left\{\left\lfloor \frac{y}{k}\right\rfloor : y \in A\right\} \subseteq \left\{\left\lfloor \frac{y}{k}\right\rfloor : y \in B\right\}$ 由于已知 $A$ 是合法的解， $A$ 已经覆盖了 $\{0, 1, \dots, a_k - 1\}$ 中的所有值，因而包含关系更大的 $B$ 必然也覆盖了 $\{0, 1, \dots, a_k - 1\}$ 中的所有值。

结合以上两点，对于每个 $k$ ， $B$ 计算出的 $\text{mex}$ 恰好就是 $a_k$ ！
因此，只需将所有禁选区间覆盖的数剔除，剩下的数构成的集合即为一组正确答案。

4. 算法实现与复杂度

对于每个 $k \in \{1, \dots, n\}$ ，如果 $1LL \cdot k \cdot a_k < n$ ，则区间 $[k \cdot a_k, \min(n - 1, k \cdot a_k + k - 1)]$ 为禁选区间。注意 $k \cdot a_k$ 可能会超过 32 位整数范围，需要用 64 位整数（long long）防止溢出。
使用差分数组（Difference Array）快速对这些区间进行区间加 1 操作。
通过一次前缀和计算每个位置被覆盖的次数，未被任何禁选区间覆盖的位置即为集合 $B$ 的元素。
单组数据时间复杂度为 $O(n)$ ，总时间复杂度为 $O(\sum n) \le O(10^5)$ ，空间复杂度为 $O(n)$ 。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 差分数组标记每个被禁止的位置
    vector<int> diff(n + 2, 0);
    for (int k = 1; k <= n; k++) {
        long long L = 1LL * k * a[k];
        if (L < n) {
            long long R = min((long long)n - 1, L + k - 1);
            diff[L]++;
            diff[R + 1]--;
        }
    }

    // 通过前缀和找出所有未被禁止的位置
    vector<int> B;
    int cur = 0;
    for (int y = 0; y < n; y++) {
        cur += diff[y];
        if (cur == 0) {
            B.push_back(y);
        }
    }

    // 输出集合大小
    cout << B.size() << "\n";
    // 输出集合元素
    for (int i = 0; i < (int)B.size(); i++) {
        cout << B[i] << (i + 1 == (int)B.size() ? "" : " ");
    }
    cout << "\n";
}

int main() {
    // 快速 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

题解

1. 问题分析与 mex\text{mex}mex 性质

2. 禁选区间

3. 贪心构造：选取最大可能集合

4. 算法实现与复杂度

C++ 代码

1. 问题分析与 $\text{mex}$ 性质