题解:
首先很容易看出各个操作是互不影响的,即对于一个合法的操作序列,我们可以任意交换两个操作的位置而不影响合法性.
因此我们可以忽略操作先后的影响,只考虑这个操作是否会出现在操作序列中.
如果用2n枚举操作集S再验证,很难有思路.
不如固定操作依次为1-n,然后进行暴搜.
由于这题特殊的性质,暴搜的状态实际并不多.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<n;i++)
#define pii pair<int,int>
#define uint unsigned int
#define FILE "dealing"
int read(){
int x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
template<class T> bool cmax(T& a,T b){return a<b?a=b,true:false;}
template<class T> bool cmin(T& a,T b){return a>b?a=b,true:false;}
const int maxn=4100,limit=128,inf=1000000000;
int a[maxn],n;
int fac[15];
int ans;
void Swap(int a[],int b[],int len){
up(i,0,len)swap(a[i],b[i]);
}
void dfs(int pos,int cnt){
if(pos==n){
ans+=fac[cnt];
return;
}
int top=0,q[3]={0,0,0};int len=1<<pos+1;
for(int i=0;i<1<<n;i+=len){
if(a[i+(len>>1)-1]+1!=a[i+(len>>1)]){
if(top==2)return;
q[++top]=i;
}
}
if(top==0){
dfs(pos+1,cnt);
return;
}
if(top==1){
int i=q[1];
if(a[i+len-1]+1==a[i]){
Swap(a+i,a+i+(len>>1),len>>1);
dfs(pos+1,cnt+1);
Swap(a+i,a+i+(len>>1),len>>1);
}
return;
}
if(top==2){
int i=q[1],j=q[2];
if(a[i+(len>>1)]==a[j+(len>>1)-1]+1&&a[j+(len>>1)]==a[i+(len>>1)-1]+1){
Swap(a+i,a+j,len>>1);
dfs(pos+1,cnt+1);
Swap(a+i,a+j,len>>1);
Swap(a+i+(len>>1),a+j+(len>>1),len>>1);
dfs(pos+1,cnt+1);
Swap(a+i+(len>>1),a+j+(len>>1),len>>1);
}
if(a[i]==a[j+(len>>1)-1]+1&&a[j+(len)-1]+1==a[i+(len>>1)]){
Swap(a+i,a+j+(len>>1),len>>1);
dfs(pos+1,cnt+1);
Swap(a+i,a+j+(len>>1),len>>1);
}
if(a[j]==a[i+(len>>1)-1]+1&&a[i+(len)-1]+1==a[j+(len>>1)]){
Swap(a+j,a+i+(len>>1),len>>1);
dfs(pos+1,cnt+1);
Swap(a+j,a+i+(len>>1),len>>1);
}
return;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read();
fac[0]=1;
up(i,1,n+1)fac[i]=fac[i-1]*i;
up(i,0,1<<n)a[i]=read();
dfs(0,0);
printf("%d\n",ans);
return 0;
}
