解题思路

关键观察

• 每个数只能不断对半下降，最终可能变为 0；因此一个数最终能变成的值集合是它不断对半后的所有值。
• 目标是让每个 1..n 都恰好被占用一次。

本题为2025年8月17日OPPO机考原题

OPPO机考的介绍点击这里

题目内容

给定一个长度为 $n$ 的整数数组 $a$ 。你可以对 $a$ 进行若干次下面的操作(可以不操作):

• 选择一个下标 $1 ≦i≦ n$，并将 $a_i$ 更新为$\lfloor \frac {a_i} {2} \rfloor$。在这里，$\lfloor x \rfloor$ 意味着对 $x$ 下取整。

小欧想知道，是否存在一个操作序列，使得在所有操作后数组 $a$ 为一个排列?

【名词解释】

长度为 $n$ 的排列是由 $1,2,...,n$ 这 $n$ 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而 {$1,2,2$} 和 {$1,3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤ T ≤ 10^4)$ 代表数据组数，每组测试数据描述如下：

第一行包含一个整数 $n(1≤n≤2×10^5)$ ，表示数组 $a$ 的长度。

第二行包含长度为 $n$ 个整数，$0≤a_i≤10^9$

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

输出 $T$ 行，其中第 $i$ 行为第 $i$ 组测试数据的答案。对于每一组测试数据，如果答案存在，在一行上输出 $YES$ ; 否则直接输出 $NO$ 。您可以以任何大小写形式输出答案。例如，字符串 $yEs、yes$ 和 $Yes$ 都将被视为肯定的回答。

样例1

输入

5
3
1 2 4
3
1 2 6
1
1
2
1 536870911
5
25752 3010 1188 126 270

输出

NO
YES
YES
NO
YES

说明

对于第 $2$ 组测试数据，我们可以对 $a_3$ 进行一次操作，数组 $a$ 变为 {$1,2,3$} ，是长度为 $3$ 的排列。