Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created October 21, 2013 04:44
Show Gist options
  • Save hiroshi-cl/7078768 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/7078768 to your computer and use it in GitHub Desktop.
2013年 夏合宿4日目 Problem F : Graph Automata Player [Licence: NYSL Version 0.9982]
import java.util.*;
public class Main {
public static void main(String... args) {
final Scanner sc = new Scanner(System.in);
// input
final int N = sc.nextInt();
final boolean[][] m = new boolean[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
m[i][j] = sc.nextInt() == 1;
final boolean[] v = new boolean[N];
for (int i = 0; i < N; i++)
v[i] = sc.nextInt() == 1;
final int T = sc.nextInt();
// pow
final boolean[][] mp = pow(m, T);
// glue code
final boolean[][] mat = new boolean[N][N + 1];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
mat[i][j] = mp[i][j];
for (int i = 0; i < N; i++)
mat[i][N] = v[i];
// elim
elim(mat);
// rank check
int rank = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (mat[i][j])
rank = i + 1;
// output
if (rank == N) { // full rank
subst(mat);
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
if (i > 0)
sb.append(' ');
sb.append(mat[i][N] ? '1' : '0');
}
System.out.println(sb);
} else
System.out.println(mat[rank][N] ? "none" : "ambiguous");
}
private static boolean[][] mul(final boolean[][] a, final boolean[][] b) {
final int m = a.length;
final int l1 = a[0].length;
final int l = b.length;
final int n = b[0].length;
if (l != l1)
throw new RuntimeException("matrix dimension error");
final boolean[][] r = new boolean[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < l; k++)
r[i][j] ^= a[i][k] & b[k][j];
return r;
}
private static boolean[][] pow(final boolean[][] m, final int p) {
if (p < 0)
throw new UnsupportedOperationException();
else {
final int n = m.length;
final int n1 = m[0].length;
if (n != n1)
throw new RuntimeException("matrix dimension error");
switch (p) {
case 0: {
final boolean[][] r = new boolean[n][n];
for (int i = 0; i < n; i++)
r[i][i] = true;
return r;
}
case 1:
return m;
default: {
final boolean[][] m2 = pow(m, p / 2);
final boolean[][] r = mul(m2, m2);
return p % 2 == 0 ? r : mul(r, m);
}
}
}
}
private static void elim(final boolean[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
for (int i = 0, j = 0; i < m && j < n; i++, j++) {
// pivot
int p = i;
while (j < n) {
while (p < m && !mat[p][j])
p++;
if (p < m)
break;
j++;
p = i;
}
if (j == n)
break;
final boolean[] v = mat[p];
mat[p] = mat[i];
mat[i] = v;
// elim
for (int k = i + 1; k < m; k++)
if (mat[k][j])
for (int l = j; l < n; l++)
mat[k][l] ^= mat[i][l];
}
}
private static void subst(final boolean[][] mat) {
final int m = mat.length;
final int m1 = mat[0].length - 1;
if (m != m1)
throw new RuntimeException("matrix dimension error");
for (int i = m - 1; i > 0; i--)
if (mat[i][m])
for (int j = i - 1; j >= 0; j--)
if (mat[j][i])
mat[j][m] ^= true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment