Submission #30246718

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
 
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define f first
#define s second
#define nl "\n"
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MOD=1e9+7;

const int N=1000001;
int n,m;
int a[N];
int A[N];

vi solve(int i, int k){
  vi ret(1<<k);
  if(i<=0) return ret;
  if(k==0){
    ret[0]=a[i];
    return ret;
  }
  vi a=solve(i, k-1);
  vi b=solve(i-(1<<(k-1)), k-1);
  rep(j,0,(1<<(k-1))-1){
    ret[j]=a[j]^b[j];
  }
  rep(j,0,(1<<(k-1))-1){
    ret[j+(1<<(k-1))]=(a[j]);
  }
  // cout << i << " " << k << nl;
  // for(int x:ret) cout << x << " ";
  //   cout << nl;
  return ret;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  rep(i,1,n){
    cin >> a[i];
    A[i]=A[i-1]^a[i];
  }

  int k=0;
  while((1<<k)<max(n,m)) k++;
  vi ret=solve(n, k);
  rep(i,0,m-1) cout << ret[i] << " ";
}
// mex?
// "moving" A a_1 a_2...a_n -> 0 1...n

Submission Info

Judge Result