fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. void FWT(vector<ll> &a, bool inv) {
  5.     int n = (int)a.size();
  6.     for(int step = 1; step < n; step <<= 1) {
  7.         for(int i = 0; i < n; i += step << 1) {
  8.             for(int j = 0; j < step; j++) {
  9.                 ll x = a[i + j];
  10.                 ll y = a[i + j + step];
  11.                 a[i + j] = x + y;
  12.                 a[i + j + step] = x - y;
  13.             }
  14.         }
  15.     }
  16.     if(inv) {
  17.         for(int i = 0; i < n; i++) a[i] /= n;
  18.     }
  19. }
  20. const int N = 200005, X = (1 << 20);
  21. int arr[N];
  22. int main() {
  23.     cin.tie(0)->sync_with_stdio(false);
  24.     int n;
  25.     cin >> n;
  26.     for(int i = 0; i < n; i++) cin >> arr[i];
  27.  
  28.     vector<int> pref(n + 1, 0);
  29.     for(int i = 0; i < n; i++) pref[i + 1] = pref[i] ^ arr[i];
  30.  
  31.     int k = (1 << 20);
  32.  
  33.     vector<ll> F(k, 0);
  34.     for(int x : pref) F[x]++;
  35.  
  36.     vector<ll> A = F;
  37.     FWT(A, 0);
  38.     for(int i = 0; i < k; i++) A[i] = A[i] * A[i];
  39.     FWT(A, 1);
  40.  
  41.     vector<int> ans;
  42.     if(A[0] > n + 1) ans.push_back(0);
  43.     for(int i = 1; i < k; i++) {
  44.         if(A[i] > 0) ans.push_back(i);
  45.     }
  46.  
  47.     cout << ans.size() << "\n";
  48.     for(auto x : ans) {
  49.         cout << x << " ";
  50.     }
  51.     cout << "\n";
  52. }
  53.  
Success #stdin #stdout 0.05s 19624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/77uyVf
language:
C++14 (clang 8.0)
created:
10 hours 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!