CF1163E Magical Permutation（线性基，构造）

虽然做起来有一点裸……但是就是想不到啊……

首先令 $d_i=p_i\oplus p_{i-1}$，那么 $d_i$ 都是 $S$ 中的数，$a_i=d_i\oplus d_{i-1}\oplus \cdots\oplus d_2$。也就是每个数都能被表示成 $S$ 的某个子集的异或和。

要用 $S$ 表示出 $1$ 到 $2^x-1$ 的所有数（不用考虑 $0$，因为每个数是可以重复用的，可以 $S_i\oplus S_i=0$）。怎么求出最大的 $x$？

其实就是建出线性基，然后最小的没有数的位就是 $x$ 了。为什么？当 $0$ 到 $x-1$ 都有数时是可以表示出所有 $0$ 到 $2^x-1$ 的，而当 $x$ 没有数时无法填第 $x$ 位。

（想用严谨一点的语言的……然而实力不允许……）

然后，求出 $x$ 后如何构造排列？

首先有最原始的想法：DFS，每次 $O(n)$ 枚举下一个数是这一个数异或上啥。肯定不可能过。

然后发现只需要保留线性无关的最大子集（可以在建线性基的过程中就完成），此时肯定还是能表示出全部的数（线性无关的定义）。同时数的个数降到了 $O(\log)$。

看起来还是不能过，但是……它的复杂度是对的！为什么？

DFS 过程中要判断 $vis[x\oplus S[i]]$，这就是在原始想法中耗费大量无用时间的原因。

而出现这样的情况，当且仅当出现了区间异或和为 $0$ 的情况。

但是对于这个线性无关的子集，会出现这样的情况，当且仅当当前枚举的 $S_i$ 等于目前的某一个后缀异或和。因为既然线性无关，所以所有不可重子集的异或和都不为 $0$。

由于 $S_i$ 只有 $O(\log)$ 种，所以也只会有 $O(\log)$ 次无法递归。

那么复杂度就对了。$O(n\log)$。下面的代码实现比较丑，所以复杂度似乎是两个 $\log$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,s[maxn],lb[],vec[],vl,ans,seq[maxn],sl;

bool vis[maxn],ok;

void insert(int x){

    int tmp=x;

    ROF(i,,) if((x>>i)&){

        if(!lb[i]){

            lb[i]=x;

            vec[++vl]=tmp;

            return;

        }

        else x^=lb[i];

    }

}

bool check(int x){

    FOR(i,,x-) if(!lb[i]) return false;

    return true;

}

void dfs(int x){

    vis[x]=true;

    seq[++sl]=x;

    if(sl==(<<ans)){ok=true;return;}

    FOR(i,,vl) if(!vis[x^vec[i]]){

        dfs(x^vec[i]);

        if(ok) return;

    }

    vis[x]=false;

    sl--;

}

int main(){

    n=read();

    FOR(i,,n) s[i]=read();

    ROF(_,,){

        MEM(lb,);MEM(vec,);vl=;

        FOR(i,,n) if(s[i]<=(<<_)-) insert(s[i]);

        if(check(_)){ans=_;break;}

    }

    printf("%d\n",ans);

    dfs();

    FOR(i,,sl) printf("%d ",seq[i]);

}

巴特西

CF1163E Magical Permutation（线性基，构造）

最新文章

热门文章