线性基例题

最大异或和,第k小异或和

  • 最大异或和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include<bits/stdc++.h>
    #define INIT(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define repd(i,a,b) for(int i=a;i>=b;--i)
    #define S(d) scanf("%d",&d)
    #define Sll(d) scanf("%lld",&d)
    #define P(d) printf("%d",d)
    #define Pll(d) printf("%lld",d)
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N=100+7;
    const int M=2e6+7;
    const int mod=1e9+7;
    ll d[N],a[N];
    int n;
    void add(ll x){
    repd(i,51,0)
    if(x&(1ll<<i)){
    if(d[i]) x^=d[i];
    else {
    d[i]=x;
    //"高斯消元,使得对于任意存在于线性基的二进制位i,至多只有一个b[j]满足第i位为 1。可求第k小异或和,最大就全异或"
    repd(k,i-1,0) if(d[k]&&(d[i]&(1ll<<k))) d[i]^=d[k];
    rep(k,i+1,51) if(d[k]&(1ll<<i)) d[k]^=d[i];
    break;
    }
    }
    }
    ll ans(){
    ll res=0;
    repd(i,51,0) res^=d[i];
    return res;
    }
    int main(){
    S(n);
    rep(i,1,n) {
    Sll(a[i]);
    add(a[i]);
    }
    Pll(ans());
    return 0;
    }
  • 第k小异或和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    #include<bits/stdc++.h>
    #define INIT(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define repd(i,a,b) for(int i=a;i>=b;--i)
    #define S(d) scanf("%d",&d)
    #define SLL(d) scanf("%lld",&d)
    #define P(d) printf("%d\n",d)
    #define PLL(d) printf("%lld\n",d)
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N=1e4+7;
    const int M=2e6+7;
    const int mod=1e9+7;
    int t,n,q,tot;
    ll a[N],d[100],k;
    void add(ll x){
    repd(i,61,0)
    if(x&(1ll<<i)){
    if(d[i]) x^=d[i];
    else {
    d[i]=x;
    tot++;
    repd(k,i-1,0) if(d[k]&&(d[i]&(1ll<<k))) d[i]^=d[k];
    rep(k,i+1,61) if(d[k]&(1ll<<i)) d[k]^=d[i];
    break;
    }

    }
    }
    ll ans(ll k){
    if(tot<n)k--;//当tot<n时整体可异或出0,但线性基里面不会
    if(k>=(1ll<<tot))return -1;//超过能异或出的数的个数上限
    ll ans=0;
    //k的第i位为1时,异或第i个线性基中的元素
    rep(i,0,61){
    if(d[i]){
    if(k&1) ans^=d[i];
    k>>=1;
    }
    }
    return ans;
    }
    int main(){
    S(t);
    rep(Case,1,t){
    printf("Case #%d:\n", Case);
    INIT(d,0);tot=0;
    S(n);
    rep(i,1,n) {
    SLL(a[i]);
    add(a[i]);
    }
    S(q);
    while(q--){
    SLL(k);
    PLL(ans(k));
    }
    }
    return 0;
    }
  • 给出一个数,求在不去重异或集合中的位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define INIT(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define repd(i,a,b) for(int i=a;i>=b;--i)
    #define S(d) scanf("%d",&d)
    #define SLL(d) scanf("%lld",&d)
    #define P(d) printf("%d\n",d)
    #define PLL(d) printf("%lld\n",d)
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N=1e5+7;
    const int M=2e6+7;
    const int mod=10086;
    const int Size=30;
    int n,q,a[N],d[100],num=0;
    int qpow(int x,int n){
    int ans=1;
    x%=mod;
    while(n){
    if(n&1) (ans*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
    }
    return ans%mod;
    }
    void add(int x){
    repd(i,Size,0)
    if(x>>i & 1){
    if(d[i]) x^=d[i];
    else {
    num++;
    d[i]=x;
    break;
    }
    }
    }
    vector<int> vec;
    int main(){
    S(n);
    rep(i,1,n){
    S(a[i]);
    add(a[i]);
    }
    S(q);
    int ans=0;
    rep(i,0,Size)
    if(d[i]) vec.push_back(i);
    rep(i,0,vec.size()-1)
    if(q>>vec[i] & 1)
    (ans+=(1<<i))%=mod;
    P((qpow(2,(n-num))%mod*ans%mod+1)%mod);
    return 0;
    }
Donate comment here