题面

题目描述

小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$ ($n<=12$)

第二行,$2^N$个整数,$A[1..2^N]$

输出格式

一个整数表示答案

输入输出样例

输入样例

3
7 8 5 6 1 2 4 3

输出样例

6

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,s[10005],bin[30],jc[20],ans=0;
bool check(int x,int len){//检查$[x,x+len−1]$这一段是不是严格按 1 递增
	for (int i=x+1;i<=x+len-1;i++){
		if (s[i]!=s[i-1]+1){
			return 0;
		}
	}
	return 1;
}
void swapp(int x,int y,int len){//交换$[x,x+len-1]$和$[y,y+len-1]$两段
	for (int i=1;i<=len;i++){
		swap(s[x+i-1],s[y+i-1]);
	}
}
void dfs(int k,int cnt){//分割为$2^k$段，在此之前操作了cnt次
	if (k==n+1&&check(1,bin[n])){//如果搜到底且有序那么计算当前操作的贡献并累计
		ans+=jc[cnt];
		return;
	}
	int tmp=0,t1=0,t2=0;
	for (int i=1;i<=bin[n];i+=bin[k]){//检测$2^k$段中的每一段是不是严格按 1 递增
		if (!check(i,bin[k])){//记录不严格递增的
			tmp++;
			if (tmp==1){
				t1=i;
			}
			if (tmp==2){
				t2=i;
			}
			if (tmp>2){//如果有 2 段以上不严格递增的，那么回溯
				return;
			}
		}
	}
	if (tmp==0){//如果没有不严格递增的就继续搜索
		dfs(k+1,cnt);
		return;
	}
	if (tmp==1){//如果有 1 段不严格递增的那么交换这一段中的前半段和后半段继续搜索
		swapp(t1,t1+bin[k-1],bin[k-1]);
		dfs(k+1,cnt+1);
		swapp(t1,t1+bin[k-1],bin[k-1]);
		return;
	}
	if (tmp==2){//如果有两段不严格递增的
 		//交换第一段的前半段和第二段的前半段继续搜索
		swapp(t1,t2,bin[k-1]);
		if (check(t1,bin[k])&&check(t2,bin[k])){
			dfs(k+1,cnt+1);
			swapp(t1,t2,bin[k-1]);
			goto second;
		}
		swapp(t1,t2,bin[k-1]);
		
		//交换第一段的后半段和第二段的前半段继续搜索
		swapp(t1+bin[k-1],t2,bin[k-1]);
		if (check(t1,bin[k])&&check(t2,bin[k])){
			dfs(k+1,cnt+1);
			swapp(t1+bin[k-1],t2,bin[k-1]);
			goto second;
		}
		swapp(t1+bin[k-1],t2,bin[k-1]);
		
		second:
			//交换第一段的前半段和第二段的后半段继续搜索
			swapp(t1,t2+bin[k-1],bin[k-1]);
			if (check(t1,bin[k])&&check(t2,bin[k])){
				dfs(k+1,cnt+1);
				swapp(t1,t2+bin[k-1],bin[k-1]);
				return;
			}
			swapp(t1,t2+bin[k-1],bin[k-1]);
			
			//交换第一段的后半段和第二段的后半段继续搜索
			swapp(t1+bin[k-1],t2+bin[k-1],bin[k-1]);
			if (check(t1,bin[k])&&check(t2,bin[k])){
				dfs(k+1,cnt+1);
				swapp(t1+bin[k-1],t2+bin[k-1],bin[k-1]);
				return;
			}
			swapp(t1+bin[k-1],t2+bin[k-1],bin[k-1]);
	}
}
int main(){
	bin[0]=1;
	for (int i=1;i<=20;i++){//预处理 2 的幂次方
		bin[i]=bin[i-1]*2;
	}
	jc[0]=1;
	for (int i=1;i<=12;i++){//预处理阶乘
		jc[i]=jc[i-1]*i;
	}
	cin>>n;
	for (int i=1;i<=bin[n];i++){
		s[i]=read();
	}
	dfs(1,0);
	cout<<ans;
}