Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

12/6
19:29
dfs

[bzoj 3990] [SDOI2015]排序

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

小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].

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行,一个整数N

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个整数表示答案

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3
7 8 5 6 1 2 4 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

很显然的是操作的顺序是没有影响的,所以按照长度从小到大考虑

在进行第i次操作以后,在进行第i+1次操作的时候,最多有2组是无序的,这里的有序定义为严格从小到大相邻。因为如果存在3组或以上的话,至少有1组在经过这次操作后还是无序的,且之后的操作不会对它产生影响,最后仍然是无序的。

所以只要根据这个去搜索就行了,讨论一下无序组数为0,1,2的情况

 

[bzoj 3990] [SDOI2015]排序