1009. Imperfect Permutation

题目描述

有一棵深度为 $n$ 的满二叉树（根节点深度为 $0$）。初始时，从左到右第 $i$ 个叶子节点的标号为 $i-1$。

你可以进行以下操作任意多次（可以不操作）：选择一个非叶子节点，交换它的左右子树。

所有操作结束后，从左到右读出叶子标号，得到长度为 $2^n$ 的序列 $a$。给定一个 $0,1,\ldots,2^n-1$ 的排列 $p$，求 $a_i=p_i$ 的位置数量的最大值。

输入格式

第一行包含一个整数 $T$（$1\le T\le 32$），表示测试数据组数。

接下来依次输入每组测试数据。每组测试数据包含两行：

• 第一行包含一个整数 $n$（$1\le n\le18$）；
• 第二行包含 $2^n$ 个整数 $p_0,p_1,\ldots,p_{2^n-1}$。

保证对于所有测试数据，$\sum 2^n\le2^{22}$，且 $p$ 是 $0,1,\ldots,2^n-1$ 的排列。

输出格式

对于每组测试数据，输出一行一个整数，表示最大重合位置数。

样例输入

3
3
0 1 2 3 7 6 5 4
3
5 7 4 3 1 0 6 2
4
9 11 13 7 5 14 8 4 6 0 12 15 1 3 10 2

样例输出

8
5
5

提示

对于第一组数据，可以与给定排列完全匹配，因此答案为 $8$。

对于第二组数据，一种最优结果为 $[6,7,4,5,1,0,3,2]$，共有 $5$ 个位置匹配。

对于第三组数据，一种最优结果为 $[10,11,8,9,15,14,13,12,6,7,5,4,1,0,3,2]$，共有 $5$ 个位置匹配。

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1009