#3901. [SDOI2015]排序

[SDOI2015]排序

[SDOI2015]排序

题目描述

小A有一个12N1-2^N的排列A[1..2N]A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1<=i<=N)i(1<=i<=N),第i中操作为将序列从左到右划分为2Ni+12^{N-i+1}段,每段恰好包括2i12^{i-1}个数,然后整体交换其中两段.

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

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

第一次操作,执行第3种操作,交换A[1..4]A[1..4]A[5..8]A[5..8],交换后的A[1..8]A[1..8][7,8,5,4,3,6,1,2][7,8,5,4,3,6,1,2].

第二次操作,执行第1种操作,交换A[3]A[3]A[5]A[5],交换后的A[1..8]A[1..8][7,8,3,4,5,6,1,2][7,8,3,4,5,6,1,2].

第三次操作,执行第2中操作,交换A[1..2]A[1..2]A[7..8]A[7..8],交换后的A[1..8]A[1..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..2^N]

输出格式

一个整数表示答案

样例 #1

样例输入 #1

3
7 8 5 6 1 2 4 3

样例输出 #1

6

提示

100%的数据, 1<=N<=12.