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; }