bzoj3990

排序

小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 Output6 Hint100%的数据, 1<=N<=12.

sol：从小段到大段搜，一段段分开后，如果有两段以上不是严格升序就挂了，如果只有一段就换一下接着搜，两段的话就是交叉互换，满足条件接着搜

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=1500;
int n,a[N];
ll ans=0,Jiec[25],Bin[15];
inline bool Check(int Pos,int K)
{
    int i;
    for(i=1;i<Bin[K];i++) if(a[Pos+i-1]+1!=a[Pos+i]) return false;
    return true;
}
inline void Swap(int P1,int P2,int K)
{
    int i;
    for(i=1;i<=Bin[K];i++) swap(a[P1+i-1],a[P2+i-1]);
}
inline void dfs(int K,int Step)
{
    if(K==n+1)
    {
        ans+=Jiec[Step]; return;
    }
    int i,op1,op2,p1=0,p2=0;
    for(i=1;i<=Bin[n];i+=Bin[K]) if(!Check(i,K))
    {
        if(!p1) p1=i;
        else if(!p2) p2=i;
        else return;
    }
    if(!p1) dfs(K+1,Step);
    else if(!p2)
    {
        Swap(p1,p1+Bin[K-1],K-1);
        dfs(K+1,Step+1);
        Swap(p1,p1+Bin[K-1],K-1);
    }
    else
    {
        for(op1=0;op1<=1;op1++) for(op2=0;op2<=1;op2++)
        {
            Swap(p1+op1*Bin[K-1],p2+op2*Bin[K-1],K-1);
            if(Check(p1,K)&&Check(p2,K))
            {
                dfs(K+1,Step+1);
                Swap(p1+op1*Bin[K-1],p2+op2*Bin[K-1],K-1);
                break;
            }
            Swap(p1+op1*Bin[K-1],p2+op2*Bin[K-1],K-1);
        }
    }
    return;
}
int main()
{
    int i;
    Jiec[0]=1; for(i=1;i<=25;i++) Jiec[i]=1ll*Jiec[i-1]*i;
    Bin[0]=1; for(i=1;i<=12;i++) Bin[i]=Bin[i-1]<<1ll;
    R(n);
    for(i=1;i<=Bin[n];i++) R(a[i]);
    dfs(1,0);
    Wl(ans);
    return 0;
}
/*
input
3
7 8 5 6 1 2 4 3
output
6
*/

View Code