[BZOJ3990]排序

排序

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

Sample Output

HINT

100%的数据, 1<=N<=12.

咱以为考了3个数论题，也不知道为啥混进来个暴搜，可能因为它得想到搜出按顺序可行方式然后全排列吧

说实话，考试的时候我连暴搜都没想出来咋暴，蒟蒻依旧很弱

言归正转，刚才也提到了要搜出按顺序也就是从第一种一直按顺序用到第n种，调换位置，然后给ans+上操作次数的阶乘

怎么按顺序搜呢？答案是模拟，也就是把小部分变成完全递增，然后向大部分扩展

在给长度为2^n-i的两部分调换位置时就必须满足所有的长度为2^n-i-1的所有部分都严格递增，因为后面的所有操作长度都比当前长，不可能再对小部分数进行调整

那么怎么找到需要交换位置的长度为2^n-i的两段呢？找到长度为2^n-i+1长度中不递增的部分，那么这些部分必须经过调换

1.如果不递增的部分多于2处那就没救了，因为你只能换1次

2.如果没有不递增的，直接搜下一个操作

3.如果不递增的部分有一个就内部给两块2^n-i交换就行了

4.如果有两块那么就有4种组合方式，看网上的题解说4种里只有一种满足，我不知道为啥，也不会证，就干脆4种方式都跑一遍

搜索的代码都又臭又长，咱也不知道为啥这个题暴搜这么快，剩下那俩题考试的时候我都打的暴搜，全超时了

 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 5000
 4 #define mann 15
 5 using namespace std;
 6 int n,ans;
 7 int mi[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
 8 int a[maxn],jc[mann]={1};
 9 bool check(int qi,int chang)
10 {
11     for(int i=qi+1;i<qi+chang;++i)
12         if(a[i]!=a[i-1]+1)  return 0;
13     return 1;
14 }
15 void huan(int qi1,int qi2,int chang)
16 {
17     for(int i=0;i<chang;++i)  swap(a[qi1+i],a[qi2+i]);
18 }
19 void sou(int cs,int tot)
20 {
21     if(cs==n+1)  {ans+=jc[tot];  return ;}
22     int len=mi[cs],jl[5]={0,0,0,0,0},js=0;
23     for(int i=1;i<=mi[n];i+=len)
24     {
25         int ls=check(i,len);
26         if(ls==0)
27         {
28             if(js>=2)  return ;
29             jl[++js]=i;
30         }
31     }
32     if(js==0)  sou(cs+1,tot);
33     if(js==1)
34     {
35         huan(jl[1],jl[1]+mi[cs-1],mi[cs-1]);
36         sou(cs+1,tot+1);
37         huan(jl[1],jl[1]+mi[cs-1],mi[cs-1]);
38     }
39     if(js==2)
40     {
41         for(int i=0;i<=1;++i)
42         {
43             for(int j=0;j<=1;++j)
44             {
45                 huan(jl[1]+i*mi[cs-1],jl[2]+j*mi[cs-1],mi[cs-1]);
46                 if(check(jl[1],mi[cs])==1&&check(jl[2],mi[cs])==1)
47                 {
48                     sou(cs+1,tot+1);
49                     huan(jl[1]+i*mi[cs-1],jl[2]+j*mi[cs-1],mi[cs-1]);
50                 }
51                 else  huan(jl[1]+i*mi[cs-1],jl[2]+j*mi[cs-1],mi[cs-1]);
52             }
53         }
54     }
55 }
56 int main()
57 {
58     scanf("%d",&n);
59     for(int i=1;i<=mi[n];++i)  scanf("%d",&a[i]);
60     for(int i=1;i<=n;++i)  jc[i]=jc[i-1]*i;
61     sou(1,0);
62     printf("%d
",ans);
63     return 0;
64 }