Link

点击打开zoj题目链接

Problem

You might have noticed that there is the new fashion among rich people to have their yards tiled with black and white tiles, forming a pattern. The company Broken Tiles is well known as the best tiling company in our region. It provides the widest choices of nice patterns to tile your yard with. The pattern is nice if there is no square of size 2 * 2, such that all tiles in it have the same color. So patterns on the figure 1 are nice, while patterns on the figure 2 are not.
The president of the company wonders whether the variety of nice patterns he can provide to the clients is large enough. Thus he asks you to find out the number of nice patterns that can be used to tile the yard of size N * M. Now he is interested in the long term estimation, so he suggests N <= 10100. However, he does not like big numbers, so he asks you to find the answer modulo P.

Mean

有一个M行N列的格子,你要把他们涂色。每个格子要么白色要么黑色,并且不能形成2×2的全白或全黑。问你有多少种涂色的方法

Analyse

显然这道题要递推,行数最多有5行,递推公式可以在程序中计算出来,但是dp的循环N太大,并且每添加一列变化都是一致的,所以可以用矩阵+快速幂加速,但是N还是太大,所以直接用Java大数好了。总的时间复杂度是O(m^6*lgn).

刚开始用Python写了半天,发现超时了,可能Python在循环层数多的时候,速度就不行了吧,包括xrange和range,都会超时。以往经验Python的运行速度要比Java快很多呀~

Java Code

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    int[][] A = new int[33][33];
    int[][] B = new int[33][33];
    int len = 0;

    int[][] mul(int[][] X, int[][] Y, int mod) {
        int[][] res = new int[33][33];
         for(int i = 0; i < len; ++i)
             for(int j = 0; j < len; ++j)
                 for(int k = 0; k < len; ++k)
                     res[i][j] = (res[i][j] + X[i][k] * Y[k][j]) % mod;
        return res;
    }

    void pow(BigInteger n, int mod) {
        for(int i = 0; i < len; ++i)
            for(int j = 0; j < len; ++j)
                B[i][j] = i==j ? 1 : 0;
        for(int i = 0, ed = n.bitLength(); i < ed; ++i) {
            if(n.testBit(i))
                B = mul(B, A, mod);
            A = mul(A, A, mod);
        }
    }

    void solve() {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while ((T--) > 0) {
            BigInteger n = cin.nextBigInteger();
            int m = cin.nextInt();
            int mod = cin.nextInt();
            len = 1 << m;
            for(int i = 0; i < len; ++i) {
                for(int j = 0; j < len; ++j) {
                    A[i][j] = 1;
                    for(int k = 0; k < m-1; ++k) {
                        int a = (i>>k)&1, b = (i>>(k+1))&1, x = (j>>k)&1, y = (j>>(k+1))&1;
                        if(a == b && a == x && b == y) {
                            A[i][j] = 0;
                            break;
                        }
                    }
                }
            }
            pow(n.subtract(BigInteger.ONE), mod);
            int sum = 0;
            for(int i = 0; i < len; ++i)
                for(int j = 0; j < len; ++j)
                    sum = (sum + B[i][j]) % mod;
            System.out.println(sum);
            if(T > 0) System.out.println();
        }
        cin.close();
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}

欢迎留言