Quad Tiling (POJ 3420)

This is a problem need applying fast matrix power technique. The fast matrix power calculation is similar to fast integer power and with divide and conquer method we can finish it in $O(\log N)$ time.

Quad Tiling is a dynamic programming problem. At first we can give the transition relationship between the state of current line with that of last line.

1. If last line is ====
   • ____
   • ==__
   • _==_
   • __==
   • ====
2. If last line is ==__
   • ====
   • __==
3. If last line is __==
   • ====
   • ==__
4. If last line is _==_
   • =__=
5. If last line is =__=
   • _==_
6. If last line is ___
   • ====

Note that every state won't transit to itself except ====. Then we can write the transition matrix and the result is value of first cell from top left of nth power of this matrix.

import java.io.*;
import java.util.*;

public class QuadTiling {
    private static int MOD = 1;
    private static int[][] multiple(int[][] A, int[][] B) {
        int[][] C = new int[A.length][B[0].length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                for (int k = 0; k < B[0].length; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    private static int[][] pow(int[][] A, int n) {
        int[][] I = new int[A.length][A.length];
        for (int i = 0; i < A.length; i++) {
            I[i][i] = 1;
        }

        while (n > 0) {
            if ((n & 1) == 1) I = multiple(I, A);
            A = multiple(A, A);
            n >>= 1;
        }
        return I;
    }

    private static void solve(int n) {
        int[][] A = {
            {1, 1, 1, 1, 0, 1},
            {1, 0, 1, 0, 0, 0},
            {1, 1, 0, 0, 0, 0},
            {1, 0, 0, 0, 1, 0},
            {0, 0, 0, 1, 0, 0},
            {1, 0, 0, 0, 0, 0}
        };

        A = pow(A, n);
        System.out.println(A[0][0]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while(in.hasNextInt()) {
            int n = in.nextInt();
            MOD = in.nextInt();

            if (n == 0) return;

            solve(n);
        }
    }
}