【题目】

【题意】给定数组b，求重排列b数组使其前缀异或和数组a单调递增。\(n \leq 10^5,1 \leq b_i \leq 2^{60}\)。

【算法】异或

为了拆位分析，先考虑一个简单的问题：已知一个合法b数组和一个数字"1"，求数字”1“是否能插入？

容易发现，”1“插入的位置必须满足前面的数字中有偶数个奇数（可以是0个），因为这样前缀和才能比上一位多1，满足要求。

进一步的，已知一个有y个奇数的合法b数组和x个数字”1“，求数字”1“能否全部插入？

利用上面的结论，容易发现当x<=y+1时，只需要在最前面放一个”1“，然后每隔一个奇数放一个”1“就能满足要求（”1“本身也是奇数）。

而当x>y+1时，无解。

上面这个结论可以扩展，对于第k位，已知有y个第k位为0的数字的合法b数组，和x个第k位为1的在\([1,2^{k+1}-1]\)范围内的数字，求数字能否全部插入？

为什么这样扩展是正确的？一个数字能否插入其实只取决于它的最高的1。因为如果最高位异或变成0，无论低位如何都不合法。如果最高为异或变成1，无论低位如何都合法。

现在考虑做法，如何在插入时保证不跳过每次前缀和为偶数的情况？预处理v[i]表示最高的”1“在第i位的数字列表，从前往后依次确定答案，从低位到高位枚举合法的位数并且数字列表不空就插入，累加前缀和。从低到高枚举就能保证插入的数字的低位一定都是不能插入的，免得低位的”1“使得跳过了前缀和为偶数的情况。

复杂度\(O(60*n)\)。

本题的关键在于从将数字插入已有的合法数列的角度考虑。

#include
    
     #include
     
      #define ll long longusing namespace std;vector
      
       v[70];int n;ll ans[100010],cur=0;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        ll u;scanf("%lld",&u);        for(int j=60;j>=0;j--)if((u>>j)&1){v[j].push_back(u);break;}    }    for(int i=1;i<=n;i++){        bool ok=0;        for(int j=0;j<=60;j++)if(!(cur&(1ll<