P3322 [SDOI2015]排序

    • 101通过
    • 231提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 排序 搜索 深度优先搜索,DFS 2015 山东
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小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第二行,2^N个整数,A[1..2^N]

    输出格式:

    一个整数表示答案

    输入输出样例

    输入样例#1: 复制
    3
    7 8 5 6 1 2 4 3
    输出样例#1: 复制
    6

    说明

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。