[SDOI2015]排序 ( 洛谷 P3322 & BZOJ 3990 )

题面

题目描述

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

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

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

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

第二次操作,执行第 $1$ 种操作,交换$A[3]$和$A[5]$,交换后的$A[1..8]$为$[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$ ($n<=12$)

第二行,$2^N$个整数,$A[1..2^N]$

输出格式

一个整数表示答案

输入输出样例

输入样例

输出样例

代码

暂无评论

发送评论


				
上一篇
下一篇