2013年 夏合宿4日目 Problem F : Graph Automata Player [Licence: NYSL Version 0.9982]

Main.java

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

}