#707. #2181. 「SDOI2015」排序

#2181. 「SDOI2015」排序

题目描述

小 A 有一个 1∼2n1 \sim 2 ^ n 的排列 A[1…2n]A[1 \ldots 2 ^ n],他希望将 AA 数组从小到大排序,小 A 可以执行的操作有 nn 种,每种操作最多可以执行一次,对于所有的 ii(1≤i≤n1 \leq i \leq n),第 ii 种操作为将序列从左到右划分为 2n−i+12 ^ {n - i + 1} 段,每段恰好包括 2i−12 ^ {i - 1} 个数,然后整体交换其中两段。小 A 想知道可以将数组 A 从小到大排序的不同的操作序列有多少个,小 A 认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同)。 下面是一个操作示例:n=3,A[1…8]=[3,6,1,2,7,8,5,4]n = 3, A[1 \ldots 8] = [3, 6, 1, 2, 7, 8, 5, 4]。
第一次操作,执行第三种操作,交换 A[1…4]A[1 \ldots 4] 和 A[5…8]A[5 \ldots 8],交换后的 A[1…8]A[1 \ldots 8] 为 [7,8,5,4,3,6,1,2][7,8,5,4,3,6,1,2];
第二次操作,执行第一种操作,交换 A[3]A[3] 和 A[5]A[5],交换后的 A[1…8]A[1 \ldots 8] 为 [7,8,3,4,5,6,1,2][7,8,3,4,5,6,1,2];
第三次操作,执行第二种操作,交换 A[1…2]A[1 \ldots 2] 和 A[7…8]A[7 \ldots 8],交换后的 A[1…8]A[1 \ldots 8] 为 [1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8]。

输入格式

第一行一个整数 nn。
第二行 2n2 ^ n 个整数,表示 A[1…2n]A[1 \ldots 2 ^ n]。

输出格式

一个整数表示答案。

3
7 8 5 6 1 2 4 3
6

数据范围与提示

1≤N≤121 \leq N \leq 12