#P3990. [SDOI2015]排序

    ID: 3195 传统题 2000ms 128MiB 尝试: 1125 已通过: 474 难度: 8 上传者: 标签>CF2400提高+/省选-深度优先搜索可行性剪枝组合枚举双射计数排列数计算

[SDOI2015]排序

题目描述

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

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

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

  • 第一次操作,执行第 33 种操作,交换 A[1..4]A[1..4] 和 A[5..8]A[5..8],交换后的 AA 为[7,8,5,4,3,6,1,2][7,8,5,4,3,6,1,2];
  • 第二次操作,执行第 11 种操作,交换 A[3]A[3] 和 A[5]A[5],交换后的 AA 为[7,8,3,4,5,6,1,2][7,8,3,4,5,6,1,2];
  • 第三次操作,执行第 22 种操作,交换 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 个整数,A1∼A2NA_1\sim A_{2^N}。

输出格式

一个整数表示答案。

3
7 8 5 6 1 2 4 3
6

数据范围

对于 100%100\% 的数据,1≤N≤121\le N\le 12。