Binarni signali

Ispitamo binarni signal, predstavljen nizom od \(n\) binarnih vrednosti (0 za uključeno, 1 za isključeno).

Treba odrediti broj uzastopnih podnizova signala čiji je XOR svih elemenata tačno 1.

Opis ulaza

Sa standardnog ulaza se učitava ceo broj \(n\) (\(1 < n < 10^5\)), a zatim, u narednoj liniji, i \(n\) vrednosti \(a_i\) (\(a_i \in \{0, 1\}, 0 \leq i < n\)).

Opis izlaza

Na standardni izlaz ispisati broj uzastopnih podnizova čiji je XOR svih elemenata tačno 1.

Primer 1

Ulaz

Izlaz

Objašnjenje

Primer 2

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <bits/stdc++.h>

using namespace std;

int count_segments(const vector<int> &a)
{
    const int n = a.size();

    map<int, int> num_prefix;
    num_prefix[0] = 1;

    int count = 0, prefix_xor = 0;
    for (int i = 0; i < n; i++) {
        prefix_xor ^= a[i];
        count += num_prefix[prefix_xor ^ 1];
        num_prefix[prefix_xor]++;
    }

    return count;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;
}

#include <bits/stdc++.h>

using namespace std;

int count_segments(const vector<int> &a)
{
    const int n = a.size();

    int count = 0;
    for (int i = 0; i < n; i++) {
        int curr_xor = 0;
        for (int j = i; j < n; j++) {
            curr_xor ^= a[j];
            if (curr_xor == 1) {
                count++;
            }
        }
    }

    return count;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;
}

#include <iostream>
#include <vector>

using namespace std;

int count_segments(const vector<int> &a)
{
    const int n = a.size();

    int count = 0;

        int even = 0, odd = 0;
        for (int i = 0; i < n; i++) {
                if (a[i] == 0) {
                        even++;
                } else {
                        int tmp = even;
                        even = odd;
                        odd = tmp + 1;
                }
                count += odd;
        }

    return count;
}


int main() 
{
        int n; cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;

        return 0;
}