#PQJ225x4112. QOJ 225_4112

    ID: 2784 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2015排序数学

QOJ 225_4112

全国青少年信息学奥林匹克

山东省省队选拔赛2015 第一轮 第一试 排序 排序 【问题描述】 小A 有一个1~2N 的排列A[1..2N],他希望将数组A 从小到大排序。小A 可 以执行的操作有N 种,每种操作最多可以执行一次。对于所有的i(1<=i<=N), 第i 种操作为:将序列从左到右划分成2N-i+1 段,每段恰好包含2i-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。 第二行,2N 个整数,A[1]、A[2]…A[2N]。 【输出格式】 一行,一个整数,表示可以将数组A 从小到大排序的不同的操作序列的个 数。 【样例输入】 3 7 8 5 6 1 2 4 3 【样例输出】 6 【数据规模和约定】 对于30%的数据,1<=N<=4; 对于全部的数据,1<=N<=12。