Submit: 651 Solved: 338
Description
小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].
Input
第一行,一个整数N
第二行,2^N个整数,A[1..2^N]
Output
一个整数表示答案
Sample Input
3
7 8 5 6 1 2 4 3
7 8 5 6 1 2 4 3
Sample Output
6
HINT
100%的数据, 1<=N<=12.
Source
DFS
思考一波可以发现，每种操作之间是互不影响的。
再思考一波发现，一种操作只能交换对应长度的两个区间，如果不单调的区间超过两个，就不可行了。
然后注意到数据范围，大概可以强行DFS
%一下神犇popoQQQ http://blog.csdn.net/popoqqq/article/details/45073989
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=5600; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int a[mxn]; 17 //int cp[mxn]; 18 int n,ed; 19 LL pw[30]; 20 LL jc[30]; 21 void init(){ 22 pw[0]=1;jc[1]=1; 23 for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2; 24 for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i; 25 return; 26 } 27 void Swap(int st1,int st2,int x){ 28 for(int i=0;i<pw[x];i++) 29 swap(a[st1+i],a[st2+i]); 30 return; 31 } 32 bool pd(int x,int k){ 33 for(int i=1;i<pw[k];i++) 34 if(a[x+i]!=a[x+i-1]+1)return 0; 35 return 1; 36 } 37 bool pd2(){ 38 for(int i=1;i<=n;i++){ 39 if(a[i]!=a[i-1]+1)return 0; 40 } 41 return 1; 42 } 43 LL ans=0; 44 void DFS(int now,int res){//2^now 总使用操作数 45 if(now>n){ 46 ans+=jc[res]; 47 return; 48 } 49 int cnt=0,pos[4]; 50 int i,j; 51 for(i=1;i<=ed;i+=pw[now]){ 52 if(!pd(i,now)){ 53 pos[++cnt]=i; 54 if(cnt>2)return; 55 } 56 } 57 if(!cnt){DFS(now+1,res);return;} 58 if(cnt==1){ 59 Swap(pos[1],pos[1]+pw[now-1],now-1); 60 DFS(now+1,res+1); 61 Swap(pos[1],pos[1]+pw[now-1],now-1); 62 } 63 else{ 64 for(i=0;i<=1;i++){ 65 bool flag=0; 66 for(j=0;j<=1 && !flag;j++){ 67 Swap(pos[1]+i*pw[now-1],pos[2]+j*pw[now-1],now-1); 68 if(pd(pos[1],now) && pd(pos[2],now)){ 69 DFS(now+1,res+1); 70 flag=1; 71 } 72 Swap(pos[1]+i*pw[now-1],pos[2]+j*pw[now-1],now-1); 73 } 74 } 75 } 76 77 } 78 int main(){ 79 n=read(); 80 init(); 81 int i,j; 82 ed=pw[n]; 83 for(i=1;i<=ed;i++){ 84 a[i]=read(); 85 } 86 DFS(1,0); 87 printf("%lld ",ans); 88 return 0; 89 }