首页 > 代码库 > ZOJ2317-Nice Patterns Strike Back：矩阵快速幂，高精度
ZOJ2317-Nice Patterns Strike Back：矩阵快速幂，高精度
Nice Patterns Strike Back
Problem Description
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 .
Input
Output
Sample Input
2 2 53 3 23
Sample Output
40
Source
1 import java.awt.Checkbox; 2 import java.io.BufferedInputStream; 3 import java.io.BufferedOutputStream; 4 import java.io.PrintWriter; 5 import java.math.BigInteger; 6 import java.util.Scanner; 7 8 public class Main { 9 10 static int p; 11 12 public static class Matrix implements Cloneable { 13 long[][] a; 14 int d; 15 16 public Matrix(int d) { 17 this.d = d; 18 a = new long[d][d]; 19 } 20 21 public Matrix multiply(Matrix m) { 22 Matrix ret = new Matrix(d); 23 for (int i = 0; i < d; ++i) { 24 for (int j = 0; j < d; ++j) { 25 for (int k = 0; k < d; ++k) { 26 ret.a[i][j] += a[i][k] * m.a[k][j]; 27 ret.a[i][j] %= p; 28 } 29 } 30 } 31 return ret; 32 } 33 34 public Matrix clone() { 35 Matrix ret = new Matrix(d); 36 ret.a = a.clone(); 37 return ret; 38 } 39 40 Matrix pow(BigInteger cnt) { 41 // 先生成一个单位矩阵 42 Matrix eye = new Matrix(d); 43 for (int i = 0; i < d; i++) 44 eye.a[i][i] = 1; 45 46 for (int i = cnt.bitLength() - 1; i >= 0; i--) { 47 eye = eye.multiply(eye); 48 if (cnt.testBit(i)) { 49 eye = eye.multiply(this); 50 } 51 } 52 return eye; 53 } 54 } 55 56 static boolean check(int x, int y, int m) { 57 for (int i = 1; i < m; i++) { 58 if ((x & 3) == (y & 3) && (x & 1) == ((x & 2) >> 1)) { 59 return false; 60 } 61 x >>= 1; 62 y >>= 1; 63 } 64 65 return true; 66 } 67 68 public static void main(String[] args) { 69 70 Scanner cin = new Scanner(new BufferedInputStream(System.in)); 71 PrintWriter cout = new PrintWriter(new BufferedOutputStream(System.out)); 72 73 int T = cin.nextInt(); 74 75 while (T-- != 0) { 76 BigInteger n = cin.nextBigInteger(); 77 int m = cin.nextInt(); 78 p = cin.nextInt(); 79 80 // 生成矩阵A 81 int d = (1 << m); 82 Matrix A = new Matrix(d); 83 for (int i = 0; i < d; i++) 84 for (int j = 0; j < d; j++) { 85 if (check(i, j, m)) 86 A.a[i][j] = 1; 87 } 88 89 A = A.pow(n.subtract(BigInteger.ONE)); 90 91 long ans = 0; 92 for (int i = 0; i < d; i++) 93 for (int j = 0; j < d; j++) { 94 ans = (ans + A.a[i][j]) % p; 95 } 96 97 cout.println(ans); 98 if (T != 0) 99 cout.println("");100 // System.out.println(ans);101 }102 103 cin.close();104 cout.close();105 106 }107 }
ZOJ2317-Nice Patterns Strike Back：矩阵快速幂，高精度