p173.ans1
======================
0110

=================
p173.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k, l;
vector<pair<int, int>> ops;
vector<pair<uint64_t, uint64_t>> constraints;
uint64_t final_row;

void read() {
    cin >> n >> m >> k >> l;
    ops.resize(m);
    for(auto& [s, d]: ops) {
        cin >> s >> d;
        s--;
    }
    constraints.resize(l);
    for(auto& [before, after]: constraints) {
        string sb, sa;
        cin >> sb >> sa;
        before = 0;
        after = 0;
        for(int i = 0; i < k; i++) {
            if(sb[i] == '1') {
                before |= (1ull << i);
            }
            if(sa[i] == '1') {
                after |= (1ull << i);
            }
        }
    }
    string s;
    cin >> s;
    final_row = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '1') {
            final_row |= (1ull << i);
        }
    }
}

void solve() {
    // The problem statement is a bit convoluted, but the key is that there is a
    // single transformation X that is valid based on the L constraints.
    // Particularly, each of the L constraint can be formalized as a linear
    // equation in Z2 - whenever A and X[1:K] match, we flip X[0] (which will
    // later be placed at X[-1] due to the cyclic shift). The variables are
    // given by A, while we already have the coefficients.
    //
    // The constraint is that L <= 200, so we can do an initial Gauss
    // elimination to find A. We don't have to, but we can use bitsets / int64_t
    // for it too to make it quicker. Afterwards, we simply need to simulate the
    // operations.
    //
    // Simulating might be a bit slow if done naively as Di <= 10^6 and we have
    // M <= 10 of these, so we should try to make each individual update
    // quickly. This can be done quickly if we keep the initial sequence and the
    // A as a bitmask / int64_t too, as then the cyclic shift and X
    // transformation ends up being a few bit operations plus a popcount which
    // is quick.

    vector<pair<uint64_t, int>> eqs(l);
    for(int i = 0; i < l; i++) {
        auto [before, after] = constraints[i];
        uint64_t coeffs = (before >> 1);
        int rhs = ((after >> (k - 1)) ^ (before & 1)) & 1;
        eqs[i] = {coeffs, rhs};
    }

    uint64_t a = 0;
    int pivot_row = 0;
    for(int col = 0; col < k - 1 && pivot_row < l; col++) {
        int found = -1;
        for(int row = pivot_row; row < l; row++) {
            if(eqs[row].first & (1ull << col)) {
                found = row;
                break;
            }
        }
        if(found == -1) {
            continue;
        }
        swap(eqs[pivot_row], eqs[found]);
        for(int row = 0; row < l; row++) {
            if(row != pivot_row && (eqs[row].first & (1ull << col))) {
                eqs[row].first ^= eqs[pivot_row].first;
                eqs[row].second ^= eqs[pivot_row].second;
            }
        }
        pivot_row++;
    }

    for(int i = 0; i < l; i++) {
        if(eqs[i].first == 0) {
            continue;
        }
        int col = __builtin_ctzll(eqs[i].first);
        if(eqs[i].second) {
            a |= (1ull << col);
        }
    }

    uint64_t mask = (1ull << k) - 1;
    uint64_t row = final_row;
    uint64_t lower_bits = (1ull << (k - 1)) - 1;
    for(int op = m - 1; op >= 0; op--) {
        int s = ops[op].first;
        int d = ops[op].second;
        for(int t = 0; t < d; t++) {
            uint64_t sub = (row >> s) & mask;
            int flip_bit = __builtin_popcountll((sub & a) & lower_bits) & 1;
            uint64_t shifted = sub ^ ((uint64_t)flip_bit << (k - 1));
            uint64_t original = ((shifted << 1) | (shifted >> (k - 1))) & mask;
            row = (row & ~(mask << s)) | (original << s);
        }
    }

    for(int i = 0; i < n; i++) {
        cout << ((row >> i) & 1);
    }
    cout << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
statement.txt
======================
173. Coins
time limit per test: 0.75 sec.
memory limit per test: 4096 KB
input: standard
output: standard



There is a row consist of N coins. Each coin lies heads up or tails up. There is also binary vector A with (K-1) dimensions.
We accomplish M operations with our coins row: we select some consecutive K coins, and apply to selected coins transformation X for Di times (i=1..M, where i is a number of operation)
The transformation X for given row C with length K means:
1. We shift the row C in one position to the left in a cyclic way.
2. Then we scan the row C from the first (leftmost) coin to (K-1)-th coin: if coin Ci lies tails up, and Ai=1, then we turn over coin Ck
Obviously, that for constant coins row with length K transformation X is fully determined by vector A. But vector A haven't given to you. You have results of transformation L rows with length K (row of coins before transformation, and row after transformation). It is guarantied that there is exactly one vector A satisfied all L conditions.
Your task is to reconstruct initial row by given row after all operations being accomplished.

Input
There is four integer numbers in the first line of input: N, M, K, L (2<=N<=50, 1<=M<=10, 1<=L<=200, 2<=K<=N).
Second line contains description of accomplished operations, M pairs of positive integer numbers Si and Di. Si is a starting point of selected coins subrow, Di is a number of iterations of transformation (Si <= N-K+1; Di <= 10^6).
There are the following L conditions determining transformation X, L blocks by two lines each: first line of each block contains a row before transformation, and the second line contains row after transformation. Each line consists of K symbols, 1 denotes tails, 0 denotes heads.
The last line contains N symbols - row of coins after all operations accomplished. i-th symbol is 1 if i-th coin lies tails up, and 0 otherwise.

Output
Write N symbols in single line of output: i-th symbol must be 1 if i-th coin of initial row laid tails up, and 0 otherwise.

Sample test(s)

Input
4 2 3 2
2 1 1 1
010
101
101
011
1010

Output
0110
Author:	Dmitry Orlov
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003








=================
p173.in1
======================
4 2 3 2
2 1 1 1
010
101
101
011
1010

=================
