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.     ll cnt = 1;
  60.     for (ll i=0;i<k/2;i++) {
  61.         ll pal = (1ll<<i) + (1ll<<(k-1-i));
  62.         if ( basis.can(pal) ) {
  63.             cnt*=2;
  64.             cnt%=MOD;
  65.         }
  66.         if ((k&1) && basis.can(pal + (1ll<<(k+1/2)))) {
  67.             cnt*=2;
  68.             cnt%=MOD;
  69.         }
  70.     }
  71.     cnt*=1ll<<basis.nullity;
  72.     ans+=cnt;
  73.     cout<<ans<<endl;
  74. }
  75.  
  76. signed main(){
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL);cout.tie(NULL);
  79. #ifndef ONLINE_JUDGE
  80.     freopen("input.txt","r",stdin);
  81.     freopen("output.txt","w",stdout);
  82. #endif
  83.  
  84.     bool calc = false;
  85.     // calc = true;
  86.     if(calc){
  87.         cout<<(1ll<<(20))<<endl;
  88.         return 0;
  89.     }
  90.     ll t=1;
  91.     cin>>t;
  92.     while(t--) {
  93.         solve();
  94.     }
  95. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/LvIO29
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!