1318: #2181. 「SDOI2015」排序

小 A 有一个 1∼2n 1 \sim 2 ^ n 1∼2​n​​ 的排列 A[1…2n] A[1 \ldots 2 ^ n] A[1…2​n​​]，他希望将 $A$ 数组从小到大排序，小 A 可以执行的操作有 $n$ 种，每种操作最多可以执行一次，对于所有的 $i$（$1\le i\le n$），第 $i$ 种操作为将序列从左到右划分为 2n−i+1 2 ^ {n - i + 1} 2​n−i+1​​ 段，每段恰好包括 2i−1 2 ^ {i - 1} 2​i−1​​ 个数，然后整体交换其中两段。小 A 想知道可以将数组 A 从小到大排序的不同的操作序列有多少个，小 A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作示例：$n=3,A[1\dots 8]=[3,6,1,2,7,8,5,4]$。
第一次操作，执行第三种操作，交换 $A[1\dots 4]$ 和 $A[5\dots 8]$，交换后的 $A[1\dots 8]$ 为 $[7,8,5,4,3,6,1,2]$；
第二次操作，执行第一种操作，交换 $A[3]$ 和 $A[5]$，交换后的 $A[1\dots 8]$ 为 $[7,8,3,4,5,6,1,2]$；
第三次操作，执行第二种操作，交换 $A[1\dots 2]$ 和 $A[7\dots 8]$，交换后的 $A[1\dots 8]$ 为 $[1,2,3,4,5,6,7,8]$。