刚看见题面有点蒙感觉除了暴搜什么都不会做。
没想到正解是搜索...
只要有一种操作不同就算不同方案，而对于一个方案，其内部顺序对结果无影响，所以求出一种后其全排列均合法，ans+=A（tot,tot）;
因为有上面这个性质所以从1搜到n，表示第i种操作的进行。
暴搜：暴力枚举端点进行交换。注意for循环中i+=长度,而不是i+=1,因为前提是先划分在选着换，不读题会很惨。T30
剪枝：一个特点：对于每种操作找出非连续序列个数如果大于2一定不合法，等于0就直接搜而不能再去换，因为这样会使顺序混乱一定不合法。
解释+具体操作：在搜第i种操作时假设小区间长度是y那么划分成Y/2个区间，每个里有两个小区间，查看它们是否是连续序列。因为下一次小区间长度就是y*2,所以
这次操作后不会有机会对其内部更改。以后就不会合法，这也是为什么非连续等于0后不能换的原因，因为换了内部一定不再合法。
count==0,直接搜下一种，==1看是否交换后合法，是搜下，否return，==2有四种情况其中1，3和2，4判断条件同而23，14不同。
tot记录使用的操作种类数。
骚操作：枚举换区间改成线段树。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=5000; ll ans,fac[15]; int n,m,a[maxn],turn[maxn],tot; void init() { fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; } void updata(int i,int j,int kp) { for(int u=0;u<kp;u++) { swap(a[i+u],a[j+u]); } } void search(int x,int y) { bool judge=0; if(x==n+1) { ans+=fac[tot]; return; } int kp=y<<1; int fir,sec,count=0,stack[5]; for(int i=1;i<=m;i+=kp) { fir=i+y-1; sec=fir+1; if(a[sec]!=a[fir]+1) { count++; stack[count]=i; if(count>2) return; } } if(!count) { search(x+1,kp); return; } if(count==1) { if(a[ stack[1] ]==a[ stack[1]+kp-1 ]+1) { tot++; updata(stack[1],stack[1]+y,y); search(x+1,kp); updata(stack[1],stack[1]+y,y); tot--; } return; } else { if(a[ stack[1]+y-1 ]+1==a[ stack[2]+y ]&&a[ stack[1]+y ]==a[ stack[2]+y-1 ]+1)//1 3&&2 4 { tot++; updata(stack[1],stack[2],y); search(x+1,kp); updata(stack[1],stack[2],y); updata(stack[1]+y,stack[2]+y,y); search(x+1,kp); updata(stack[1]+y,stack[2]+y,y); tot--; } if(a[ stack[1]+kp-1 ]+1==a[ stack[2]+y ]&&a[ stack[1]+y-1 ]+1==a[ stack[2] ])//2 3 { tot++; updata(stack[1]+y,stack[2],y); search(x+1,kp); updata(stack[1]+y,stack[2],y); tot--; } if(a[ stack[1] ]==a[ stack[2]+y-1 ]+1&&a[ stack[2]+kp-1 ]+1==a[ stack[1]+y ]) { tot++; updata(stack[1],stack[2]+y,y); search(x+1,kp); updata(stack[1],stack[2]+y,y); tot--; } return; } } int main() { scanf("%d",&n); init(); m=1<<n; for(int i=1;i<=m;i++) scanf("%d",&a[i]),turn[i]=a[i]; sort(turn+1,turn+1+m); int len=unique(turn+1,turn+1+m)-(turn+1); for(int i=1;i<=m;i++) { a[i]=lower_bound(turn+1,turn+1+len,a[i])-(turn); } search(1,1); printf("%lld",ans); }
总结：一种算法，有可能能优化一定要去想。
全局变量慎用，考虑清楚。
数组稍开大点。
想到思路要敢打。
不能yy比如1，3和2，4一样但23，14判断条件其实不同。
数据结构优化。