problemId=1317">http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=1317

给出一个n*m的矩阵(n <= 10^100, m <= 5)，对于2*2的子方格若全是黑色或全是白色的是非法的，用黑白两色去染n*m的方格，问共同拥有多少种合法的染色方案。

构造出转移矩阵，上一行向下一行的转移矩阵。由于m<=5，每行最多有32个状态。能够进行状态压缩构造出一个32*32的转移矩阵A。A[i][j] = 1表示上一行i状态能够向下一行的j状态转移。否则不能转移。要求最后的合法方案数，就再构造一个B矩阵，是一个32*1的矩阵，表示了到达第一行每个状态的方案数。那么A*B就表示到达第二行每个状态的方案数。以此类推。A^n-1 * B表示到达第n行每个状态的合法方案数，那么全部状态相应方案数的和就是总的方案数。

由于n特别大。要用到大数。我存矩阵的时候開始定义的大数类，一直T。改成了int型才A，1s+，难道大数类这么慢么，5s都过不了。

import java.io.*;

import java.math.BigInteger;

import java.util.Scanner;

class Matrix

{

	public int [][] mat = new int[35][35];

	public Matrix()

	{

	}

	public void init()

	{

		for(int i = 0; i < 35; i++)

		{

			for(int j = 0; j < 35; j++)

			{

				if(i == j)

					mat[i][j] = 1;

				else mat[i][j] = 0;

			}

		}

	}

}

public class Main {

	public static Matrix A,B,res;

	public static BigInteger n;

	public static int m,p,test,mm;

	static Scanner cin = new Scanner(System.in);

	public static void buildA()

	{

		for(int i = 0; i < mm; i++)

		{

			for(int j = 0; j < mm; j++)

			{

				String s1 = Integer.toBinaryString(i);

				String s2 = Integer.toBinaryString(j);

				String ss1 = new String();

				String ss2 = new String();

				for(int k = 0; k < m-s1.length(); k++)

					ss1 += '0';

				ss1 += s1;

				for(int k = 0; k < m-s2.length(); k++)

					ss2 += '0';

				ss2 += s2;

				int flag = 0;

				for(int k = 0; k < m-1; k++)

				{

					if(ss1.charAt(k)-'0' == 0 && ss1.charAt(k+1)-'0' == 0

					&& ss2.charAt(k)-'0' == 0 && ss2.charAt(k+1)-'0' == 0)

					{flag = 1;break;}

					if(ss1.charAt(k)-'0' == 1 && ss1.charAt(k+1)-'0' == 1

					&& ss2.charAt(k)-'0' == 1 && ss2.charAt(k+1)-'0' == 1)

					{flag = 1;break;}

				}

				if(flag == 1)

					A.mat[i][j] = 0;

				else A.mat[i][j] = 1;

			}

		}

	}

	public static Matrix Mul(Matrix x,Matrix y)

	{

		Matrix ans = new Matrix();

		for(int i = 0; i < mm; i++)

		{

			for(int k = 0; k < mm; k++)

			{

				if(x.mat[i][k] == 0)

					continue;

				for(int j = 0; j < mm; j++)

				{

					ans.mat[i][j] = (ans.mat[i][j]+x.mat[i][k]*y.mat[k][j])%p;

				}

			}

		}

		return ans;

	}

	public static Matrix Pow(Matrix tmp,BigInteger nn)

	{

		Matrix ans = new Matrix();

		ans.init();

		while(nn.compareTo(BigInteger.ZERO) > 0)

		{

			if( nn.remainder(BigInteger.valueOf(2)).compareTo(BigInteger.ONE) == 0)

				ans = Mul(ans,tmp);

			nn = nn.divide(BigInteger.valueOf(2));

			tmp = Mul(tmp,tmp);

		}

		return ans;

	}

	public static void main(String[] args) throws IOException

	{

		int test = cin.nextInt();

		while((test--) > 0)

		{

			n = cin.nextBigInteger();

			m = cin.nextInt();

			p = cin.nextInt();

			mm = (1<<m);

			A = new Matrix();

			B = new Matrix();

			buildA();

			for(int i = 0; i < mm; i++)

				B.mat[i][0] = 1;

			res = Pow(A,n.subtract(BigInteger.ONE));

			res = Mul(res,B);

			int anw = 0;

			for(int i = 0; i < mm; i++)

			{

				anw = (anw+res.mat[i][0])%p;

			}

			System.out.println(anw);

			if(test > 0)

				System.out.println();

		}

	}

}