[SDOI2015] 排序

题目描述

小 A 有一个 $1\sim 2^N$ 的排列 $A_1\sim A_{2^N}$，他希望将 $A$ 数组从小到大排序,小 $A$ 可以执行的操作有 $N$ 种，每种操作最多可以执行一次，对于所有的 $i(1\le i\le N)$，第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段，每段恰好包括 $2^{i-1}$ 个数,然后整体交换其中两段。

小 A 想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个。小 A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作事例: $N=3,A=[3,6,1,2,7,8,5,4]$。

• 第一次操作，执行第 $3$ 种操作，交换 $A[1..4]$ 和 $A[5..8]$，交换后的 $A$ 为$[7,8,5,4,3,6,1,2]$。
• 第二次操作，执行第 $1$ 种操作，交换 $A[3]$ 和 $A[5]$，交换后的 $A$ 为$[7,8,3,4,5,6,1,2]$。
• 第三次操作，执行第 $2$ 种操作，交换 $A[1..2]$ 和 $A[7..8]$，交换后的 $A[1..8]$ 为$[1,2,3,4,5,6,7,8]$。

输入格式

第一行，一个整数 $N$。

第二行，$2^N$ 个整数，$A_1\sim A_{2^N}$。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

3
7 8 5 6 1 2 4 3

样例输出 #1

6

提示

$100\%$ 的数据, $1\le N\le 12$。

# [SDOI2015] 排序

## 题目描述

小 A 有一个 $1\sim 2^N$ 的排列 $A_1\sim A_{2^N}$，他希望将 $A$ 数组从小到大排序,小 $A$ 可以执行的操作有 $N$ 种，每种操作最多可以执行一次，对于所有的 $i(1\le i\le N)$，第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段，每段恰好包括 $2^{i-1}$ 个数,然后整体交换其中两段。

小 A 想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个。小 A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作事例: $N=3,A=[3,6,1,2,7,8,5,4]$。
- 第一次操作，执行第 $3$ 种操作，交换 $A[1..4]$ 和 $A[5..8]$，交换后的 $A$ 为$[7,8,5,4,3,6,1,2]$。
- 第二次操作，执行第 $1$ 种操作，交换 $A[3]$ 和 $A[5]$，交换后的 $A$ 为$[7,8,3,4,5,6,1,2]$。
- 第三次操作，执行第 $2$ 种操作，交换 $A[1..2]$ 和 $A[7..8]$，交换后的 $A[1..8]$ 为$[1,2,3,4,5,6,7,8]$。

## 输入格式

第一行，一个整数 $N$。

第二行，$2^N$ 个整数，$A_1\sim A_{2^N}$。

## 输出格式

一个整数表示答案。

## 样例 #1

### 样例输入 #1

3 7 8 5 6 1 2 4 3

### 样例输出 #1

6

## 提示

$100\%$ 的数据, $1\le N\le 12$。