【bzoj3990】[SDOI2015]排序

2015年4月23日2,1233

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.

题解

膜拜PoPoQQQ大爷:

题目大意:给定一个长度为2^n的排列,有n个操作,第i个操作为【将序列分成2^(n-i+1)段,每段长2^(i-1),然后任选两段交换】,每个操作最多用一次,求有多少操作序列能把序列排出来

Orz dzy

首先我们很容易发现一个操作序列是否合法与序列的顺序是无关的

因此我们只需要确定某个操作序列中每个操作选不选就行了 那么这类操作序列对答案的贡献就是选择的操作数的阶乘

我们从小到大DFS,对于第i次操作我们将序列分成2^(n-i)段,每段长度2^i

我们找到序列中不是连续递增的段,如果这样的段超过2个,显然就废了

如果没有这样的段,就不需要执行这个操作

如果有一个这样的段,判断将这个段的前半部分和后半部分交换后是否连续递增,如果是就交换然后继续DFS

如果有两个这样的段,判断四种交换情况然后DFS

似乎只有一种情况可能合法?

 

  • qdez2015年7月27日 下午3:15 回复

    不是只有一种情况 比如 1 4 3 2

    #1  
  • DQSSSSS菌2016年2月23日 下午4:16 回复

    程序是不是错了?输入2 1 4 2 3,应该是0,您的输出2

    #2  
    • hzwer2016年3月6日 上午12:40 回复
      admin

      要确认最终序列合法性。。。
      已更正

      #21