BZOJ3990 排序

题目：www.lydsy.com/JudgeOnline/problem.php?id=3990

这题很不错。

刚开始时无从下手，想了好多$O((2^n)log(2^n))$ 的idea，但是都不行。

后来去看题解发现操作序列是满足交换率的，然后竟然是搜索。

因为swap是swap的逆运算（歪歪的）

然后只要从小到大枚举操作序列就可以了。

这样类似分治下去，当你在计算长度为$2^i$的序列时已经保证了所有长度为$2^{i-1}$的序列的「连续且递增」。

注意是「连续且递增」，开始W了好多发，然后推掉重写（开抄） 呜呜。

好像可以证明是$O(n \cdot 2^{2n})$ ？

以后见到这种操作数很小的题目要想想搜索，就算是暴力也可以多拿分。

#include <cstdio>
#include <cstring>
#include <vector>#define LL long long
#define N 13using namespace std;int n;
LL fact[],ans;void change(vector<int> &x,int l1,int l2,int len){
    for(int i=;i<len;i++)
        swap(x[l1+i],x[l2+i]);
}bool check(vector<int> x,int l,int len){
    for(int i=;i<len;i++)
        if(x[l+i]!=x[l+i-]+) return ;
    return ;
}void dfs(vector<int> x,int t,int now){
    if(t==n){
        ans+=fact[now];
        return;
    }
    int tot=,a[];
    for(int i=;i<(<<n);i+=(<<(t+)))
        if(!check(x,i,<<(t+))){
            if(tot==) return;
            a[++tot]=i; a[++tot]=i+(<<t);
        }
    vector<int> b;
    if(!tot) dfs(x,t+,now);
    if(tot==){
        if(x[a[]]+(<<t)==x[a[]]){
            b=x;
            change(b,a[],a[],<<t);
            dfs(b,t+,now+);
        }
    }
    if(tot==){
        if(x[a[]]+(<<t)==x[a[]] && x[a[]]+(<<t)==x[a[]]){
            b=x;
            change(b,a[],a[],<<t);
            dfs(b,t+,now+);
        }
        if(x[a[]]+(<<t)==x[a[]] && x[a[]]+(<<t)==x[a[]]){
            b=x;
            change(b,a[],a[],<<t);
            dfs(b,t+,now+);
        }
        if(x[a[]]+(<<t)==x[a[]] && x[a[]]+(<<t)==x[a[]]){
            b=x;
            change(b,a[],a[],<<t);
            dfs(b,t+,now+);
        }
        if(x[a[]]+(<<t)==x[a[]] && x[a[]]+(<<t)==x[a[]]){
            b=x;
            change(b,a[],a[],<<t);
            dfs(b,t+,now+);
        }
    }
}vector<int> a;int main(){
    scanf("%d",&n);
    a.resize(<<n);
    for(int i=;i<(<<n);i++) scanf("%d",&a[i]);
    fact[]=;
    for(int i=;i<=;i++) fact[i]=fact[i-]*(LL)i;
    dfs(a,,);
    printf("%lld\n",ans);
    return ;
}