「题目描述」
小A 有一个 $1-2^N$ 的排列 $A[1 \dots 2^N]$ ，他希望将 $A$ 数组从小到大排序。
小A 可以执行的操作有 $N$ 种，每种操作最多可以执行一次，对于所有的 $i(1 \leq i \leq N)$，第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段，每段恰好包括 $2^{i-1}$个数，然后整体交换其中两段。
小A 想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个，小A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。
下面是一个操作事例:
$N=3, A[1 \dots 8] = [3, 6, 1, 2, 7, 8, 5, 4]$
第一次操作，执行第 3 种操作，交换 $A[1 \dots 4]$ 和 $A[5 \dots 8]$，交换后的 $A[1 \dots 8]$为 $[7,8,5,4,3,6,1,2]$ 。
第二次操作，执行第 1 种操作，交换 $A[3]$ 和 $A[5]$ ，交换后的 $A[1 \dots 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] $。
「题目链接」
BZOJ 3990 排序 「SDOI 2015」
「 解题思路」
首先我们~~（根本不能）~~发现：操作序列中顺序是不重要的。
直观理解的话，就是各项操作交换的块是完全包含或完全分离的，所以不会出现进行一个操作导致另一个操作无法进行的情况。
这样的话，我们就可以对操作序列 定序，然后贡献乘上长度的阶乘就可以了。
我们按从小到大考虑 $1 \dots N$ 这些操作，进行 $DFS$。
我们知道，第 $i$ 次操作只能交换长度为 $2^{i - 1}$ 的块，那么为了保证最后有序，在这次交换以前，所有块的 内部 必须是有序的，不然方案必定不合法，因为之后的操作没法改变这个大小的块 内部 的顺序。
所以要在 $DFS$ 的过程中保证这一点：在第 $i$ 次交换后，所有长度为 $2^{i}$ 的块内部有序。
因为一次交换最多改变两个块的有序状态，所以最多将两个不合法的块交换成合法。
每次 $DFS$ 时先扫描整个序列，记录不合法块的位置和数量。如果其数量为 1，则尝试交换该块的两半；数量为 2，则尝试四个 半个块 两两交换，共 4 种情况；如果数量大于 2，则这种情况下无解。
复杂度粗看是 $O(n4^n)$，但其实 4 种情况种最多 1 种成立，所以其实是 $O(n^2)$。
总结：自己没有想到定序，以后遇到这种天然带有顺序的操作要尝试想一下操作顺序的影响。
「AC 代码」
#include <iostream>
#include <vector>
const int MAXN = 12;
int a[1 << MAXN];
int pow[MAXN + 1], fact[MAXN + 1];
int n;
inline void init(){
pow[0] = 1;
for(int i = 1; i <= MAXN; i++) pow[i] = pow[i - 1] << 1;
fact[0] = 1;
for(int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i;
}
inline bool check(int begin, int len){
for(int i = 1; i < len; i++){
if(a[begin + i] != a[begin + i - 1] + 1) return false;
}
return true;
}
inline void swap(int x, int y, int len){
for(int i = 0; i < len; i++) std::swap(a[x + i], a[y + i]);
}
inline void find(int len, std::vector<int> &vec){
for(int i = 0; i < pow[n]; i += len){
if(!check(i, len)){
vec.push_back(i);
if(vec.size() > 2) return;
}
}
}
long long ans;
inline void dfs(int i, int cnt){
if(i == n + 1){
ans += fact[cnt];
} else{
int len = pow[i - 1];
std::vector<int> vec;
find(2 * len, vec);
if(vec.empty()){
dfs(i + 1, cnt);
} else if(vec.size() == 1){
int x = vec[0];
swap(x, x + len, len);
if(check(x, 2 * len)) dfs(i + 1, cnt + 1);
swap(x, x + len, len);
} else if(vec.size() == 2){
int x = vec[0], y = vec[1];
for(int a = 0; a <= 1; a++) for(int b = 0; b <= 1; b++){
int xi = x + a * len, yi = y + b * len;
swap(xi, yi, len);
if(check(x, len * 2) && check(y, len * 2)) dfs(i + 1, cnt + 1);
swap(xi, yi, len);
}
}
}
}
inline long long solve(){
ans = 0;
dfs(1, 0);
return ans;
}
int main(){
init();
std::cin >> n;
for(int i = 0; i < pow[n]; i++) std::cin >> a[i];
std::cout << solve() << std::endl;
return 0;
}
就是这样啦～