fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define all(x) x.begin(),x.end()
  6.  
  7. ll MOD = 1000000007;
  8.  
  9. ll oo = 1e15;
  10.  
  11. struct XorBasis {
  12.     static const ll LOG = 60;
  13.     ll bases[LOG];
  14.     void init() {
  15.         for (ll i=0;i<LOG;i++) {
  16.             bases[i] = 0;
  17.         }
  18.     }
  19.     ll nullity = 0;
  20.     void insert(ll x) {
  21.         for (ll i=LOG-1;i>=0;i--) {
  22.             ll bit = (1ll<<i);
  23.             if ( bit&x ) {
  24.                 if (bases[i]) {
  25.                     x^=bases[i];
  26.                 }else {
  27.                     bases[i] = x;
  28.                     return;
  29.                 }
  30.             }
  31.         }
  32.         nullity++;
  33.     }
  34.     bool can(ll x) {
  35.         for (ll i=LOG-1;i>=0;i--) {
  36.             ll bit = (1ll<<i);
  37.             if ( bit&x ) {
  38.                 if (bases[i]) {
  39.                     x^=bases[i];
  40.                 }else {
  41.                     return false;
  42.                 }
  43.             }
  44.         }
  45.         return true;
  46.     }
  47. };
  48.  
  49. void solve() {
  50.     XorBasis basis;
  51.     basis.init();
  52.     ll n,k;cin>>n>>k;
  53.     ll a[n];
  54.     for (ll i=0;i<n;i++) {
  55.         cin>>a[i];
  56.         basis.insert(a[i]);
  57.     }
  58.     ll ans = -1;
  59.     for (ll i=0;i<(1ll<<(k/2));i++) {
  60.         ll reverse = 0;
  61.         ll i2 = i;
  62.         for (ll j=0;j<k/2;j++){
  63.             reverse = (reverse<<1) + (i2&1);
  64.             i2/=2;
  65.         }
  66.         ll ch1 = (reverse<<(k/2+1)) + (1ll<<k/2) + i;
  67.         ll ch2 = (reverse<<(k/2+1)) +  i;
  68.         ll ch3 = (reverse<<(k/2)) +  i;
  69.         if (k&1) {
  70.             if (basis.can(ch1)) {
  71.                 ans+=(1ll<<basis.nullity);
  72.                 ans%=MOD;
  73.             }
  74.             if (basis.can(ch2)) {
  75.                 ans+=(1ll<<basis.nullity);
  76.                 ans%=MOD;
  77.             }
  78.         }else {
  79.             if (basis.can(ch3)) {
  80.                 ans+=(1ll<<basis.nullity);
  81.                 ans%=MOD;
  82.             }
  83.         }
  84.  
  85.     }
  86.     cout<<ans<<endl;
  87. }
  88.  
  89. signed main(){
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(NULL);cout.tie(NULL);
  92. #ifndef ONLINE_JUDGE
  93.     freopen("input.txt","r",stdin);
  94.     freopen("output.txt","w",stdout);
  95. #endif
  96.  
  97.     bool calc = false;
  98.     // calc = true;
  99.     if(calc){
  100.         cout<<(1ll<<(20))<<endl;
  101.         return 0;
  102.     }
  103.     ll t=1;
  104.     cin>>t;
  105.     while(t--) {
  106.         solve();
  107.     }
  108. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/eNwrCJ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!