The transformation X contains two steps:

• Cyclic left shift
• Turn over (totally several times) k-th coin if i-th coin and A[i] are both 1 (i = 1.. k-1)

The problem also provides us L conditions. Suppose the coins are ordinarily U = [u1, u2, ..., uk], and finally become V = [v1, v2, ..., vk]. Without loss of generality, here we assume k = 4. The shift operation can be represented as a matrix

    [0 0 0 1]
S = |1 0 0 0|
    |0 1 0 0|
    [0 0 1 0]

The vector US represents U after shifting one bit left. Remember: each addition as well as multiplication is followed by modulo 2.

The second step in the transformation can be represented as a matrix too

    [1 0 0 a0]
A = |0 1 0 a1|
    |0 0 1 a2|
    [0 0 0  1]

Therefore, we have the equation USA = V. Then use Partitioned Matrix to extract X = [a0 a1 a2]. Partition U as U = [u1 u2 ... | uk], V as V = [v1 v2 ... | vk], S and A as follows

    [0 0 0 | 1]
    |1 0 0 | 0|
S = |0 1 0 | 0|
    |------+--|  
    [0 0 1 | 0]

    [1 0 0 | a0]
    |0 1 0 | a1|
A = |0 0 1 | a2|
    |------+---|
    [0 0 0 |  1]

Symbolize the equation as
(Ua Ub) (S1 S2; S3 0) (I X; 0 1) = (Va Vb)

Simplify it as
Ua*(S1*X + S2) + (Ub*S3*X) = Vb

It means that [u2 u3 ... uk]X = vk - u1

We know L equations like that, so we can use Gaussian elimination to solve X.

Now if we already know V, U can be obtained by U = V*A^(-1)*S^(-1). It can be seen that A^(-1) = A and S^(-1) = S^T, so U = V*A*S^T. In this way, the initial coins can be solved backwards. However, as the Di can be as large as 10^6, we should use 2k-ary method (Brauer, 1939) to calculate V*(A*S^T)^Di.

The code of this problem has been hosted on GitHub yuhc/sgu-solution. It’s also attached here.

/* SGU ID:  #173
 * Type  :  Gaussian Elimination
 * Author:  Hangchen Yu
 * Date  :  05/29/2015
 */
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>

using namespace std;

#define MAXN    60
#define MAXM    20
#define MAXL    210

int n, m, k, l;
int a[MAXL][MAXN], b[MAXL];
int x[MAXN];

void Gaussian() {
    for (int i = 1; i < k; i++) {
        int j = i;
        if (!a[i][j]) {
            for (int t = i+1; t <= l; t++)
                if (a[t][j]) {
                    for (int p = j; p < k; p++)
                        swap(a[i][p], a[t][p]);
                    swap(b[i], b[t]);
                    break;
                }
        }

        for (int t = i+1; t <= l; t++)
            if (a[t][j]) {
                for (int p = j; p < k; p++)
                    a[t][p] ^= a[i][p];
                b[t] ^= b[i];
            }
    }
    
    x[k-1] = b[k-1];
    for (int i = k-2; i >= 1; i--) {
        for (int j = i+1; j < k; j++)
            b[i] ^= x[j] & a[i][j];
        x[i] = b[i];
    }
}

int  C[MAXN][MAXN];
int  u[MAXN], v[MAXN];
long Di;

void fast_power() {
    int FC[MAXN][MAXN], tmp[MAXN][MAXN];
    memset(FC, 0, sizeof(FC));
    for (int i = 1; i <= k; i++) FC[i][i] = 1;

    int count_a[30], lc = 0;
    while (Di > 0) {
        count_a[lc++] = Di & 1;
        Di >>= 1;
    }
    for (int cc = lc-1; cc >= 0; cc--) {
        memset(tmp, 0, sizeof(tmp));
        for (int i = 1; i <= k; i++)
           for (int j = 1; j <= k; j++)
               for (int t = 1; t <= k; t++)
                   tmp[i][j] ^= FC[i][t] & FC[t][j];
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= k; j++)
                FC[i][j] = tmp[i][j];

        if (count_a[cc]) {
           memset(tmp, 0, sizeof(tmp));
           for (int i = 1; i <= k; i++)
               for (int j = 1; j <= k; j++)
                   for (int t = 1; t <= k; t++)
                       tmp[i][j] ^= FC[i][t] & C[t][j];
            for (int i = 1; i <= k; i++)
                for (int j = 1; j <= k; j++)
                    FC[i][j] = tmp[i][j];
        }
    }

    memset(u, 0, sizeof(u));
    for (int j = 1; j <= k; j++)
        for (int t = 1; t <= k; t++)
            u[j] ^= v[t] & FC[t][j];
}

int main() {
    int  s[MAXM];
    long d[MAXM];
    scanf("%d%d%d%d", &n, &m, &k, &l);
    for (int i = 0; i < m; i++)
        scanf("%d%ld", s+i, d+i);
    char line[MAXN];
    for (int i = 1; i <= l; i++) {
        scanf("%s", line);
        for (int j = 1; j < k; j++)
            a[i][j] = line[j] - '0';
        b[i] = -line[0];
        scanf("%s", line);
        b[i] += line[k-1];
        b[i] = (b[i]+2) % 2;
    }

    // aX = b, a is a L*(K-1) matrix, b is a L-dim vector
    // X is the binary (K-1)-dim vector A
    Gaussian();

    // U = V * inv(A) * inv(S)
    //   = V * A * S^T
    int A[MAXN][MAXN], S[MAXN][MAXN];
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            if (i == j) A[i][j] = 1;
            else if (j == k) A[i][j] = x[i];
            else A[i][j] = 0;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            S[i][j] = ((i == 1 && j == k) || (i > 1 && i == j + 1));
    
    // C = A * S^T
    for (int i = 1; i <= k; i++)
        for (int j = i+1; j <= k; j++)
            swap(S[i][j], S[j][i]);
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++) {
            C[i][j] = 0;
            for (int t = 1; t <= k; t++)
                C[i][j] ^= A[i][t] & S[t][j];
        }

    // U = V * C^Di
    scanf("%s", line);

    for (int i = m-1; i >= 0; i--) {
        Di = d[i];
        for (int j = 1; j <= k; j++)
            v[j] = line[s[i]-1+j-1] - '0';
        fast_power();
        for (int j = 1; j <= k; j++)
            line[s[i]-1+j-1] = u[j] + '0';
    }
    
    printf("%s\n", line); 
    return 0;
}