题解：P4869 albus就是要第一个出场

原题传送门

题意说得很绕，简单来说就是给一个长度为

n

序列，将

2^n

个原序列子集的异或和进行排序，让你求出某个元素在排序后序列里的第一个出现位置。

把这些数依次插入线性基。

假如现在我们找到某个子集的异或和为

x

。考虑还有什么别的方案使异或和也为

x

。

我们尝试插入另一个不在线性基里面的元素参与计算，并使异或和不变。

根据线性基的定义，我们插入的这个数一定能够用线性基里面的若干个数异或得到。这些数有一些已经参与计算了，使这些数不参与计算，另外没有参与计算的数则参与计算。这样，异或和仍然为

x

。

所以对于一个可能的异或和，无论不在线性基里的数怎么选都一定可以达到。

令线性基里有

cnt

个数，那么每个异或和至少有

2^{n-cnt}

中方式凑出来。

而可能的异或和共

2^{cnt}

种，每种

2^{n-cnt}

个，共

2^n

个，恰好等于总数。因此确定了上界。

总结一下，每个元素出现次数一样，出现

2^{n-cnt}

次。

分析

Q

的二进制位就能得到这个元素是第几大的。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
int n,q,s,p[70],a[N];
int cnt,ans;
inline void insert(int x){
    for(int i=63;i>=0;i--){
        if((x>>i)&1ll){
            if(p[i]==0){
                p[i]=x;
                cnt++;
                return;
            }
            x^=p[i];
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    cin>>q;
    s=1;
    for(int i=1;i<=n-cnt;i++) (s<<=1)%=10086;
    int sum=1;
    for(int i=0;i<=63;i++) {
        if(p[i]){
            if((q>>i)&1ll) ans|=sum;
            sum<<=1ll;
        }
    }
    ans%=10086;
    ans*=s;
    ans%=10086;
    cout<<(ans+1)%10086;
    return 0;
}

题解：P4869 albus就是要第一个出场

文章操作

原题传送门

相关推荐

评论

题解：P4869 albus就是要第一个出场