飞机票http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1317

题意很清楚，就是给你n*m矩阵，求其中不包括2*2一样颜色的方案数ans%P

因为n很大，m很小，所以很容易想到肯定要对n进行一种特殊的处理。因为第i行和第i-1行的状态有关。所以可以用第i-1行的状态来求第i行，容易想到矩阵快速幂，但是矩阵的构造有点复杂，因为一行一共有2^m=t种状态，所以可以用状态压缩，则我们可以t*t的矩阵，其中matrix i_j表示第k行的状态和k+1行在状态为i和j的时候是否符合题意。现在我们就可以矩阵快速幂了，令A=[1,1....1]表示初始状态，则A*matrix为第二种状态，其中所有元素所和即为答案，所以第n中状态就是A*（matrix）^(n-1) 对后者进行矩阵快速幂，求出答案(用到java大数

import java.math.BigInteger;
import java.util.*;
public class Main {
	
	public static BigInteger two;
	public static int len;
	public static int P;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sca=new Scanner(System.in);
		int T=sca.nextInt();
		two=new BigInteger("2");
		while(T>0){
			T--;
			BigInteger n=sca.nextBigInteger();
			n=n.subtract(BigInteger.ONE);
			int m=sca.nextInt();
			 P=sca.nextInt();
			len=(int) Math.pow(2, m);
			if(n.compareTo(BigInteger.ZERO)==0){
				System.out.println(len);
				if(T!=0)
				System.out.println();
				continue;
			}
			Matrix a=new Matrix();
			for(int i=1;i<=len;i++){
				for(int j=1;j<=len;j++){
					int l=i-1;
					int r=j-1;
					String str1=Integer.toBinaryString(l);
					String str2=Integer.toBinaryString(r);
					while(str1.length()!=m)str1="0"+str1;
					while(str2.length()!=m)str2="0"+str2;
					str1="0"+str1;
					str2="0"+str2;
					boolean flag=true;
					for(int k=1;k<m;k++){
						int ok=1;
						if(str1.charAt(k)!=str1.charAt(k))ok=0;
						if(str1.charAt(k)!=str2.charAt(k))ok=0;
						if(str1.charAt(k)!=str1.charAt(k+1))ok=0;
						if(str1.charAt(k)!=str2.charAt(k+1))ok=0;
						if(ok==1){
							flag=false;
							break;
						}
						
					}
					if(flag){
						a.mat[i][j]=1;
					}
					else{
						a.mat[i][j]=0;
					}
				}
			}
			
				Matrix ans=Poww(a,n);
				int as=0;
				for(int i=1;i<=len;i++){
					for(int j=1;j<=len;j++){
						as=(as+ans.mat[i][j])%P;
					}
				}
				System.out.println(as);
				if(T!=0)
				System.out.println();
		}
	}
	public static Matrix MUL(Matrix a,Matrix b){
		Matrix c=new Matrix();
		for(int i=1;i<=len;i++){
			for(int j=1;j<=len;j++){
				for(int k=1;k<=len;k++){
					c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%P;
				}
			}
		}
		return c;
	}
	public static Matrix Poww(Matrix a,BigInteger b){
	    Matrix ans=new Matrix();
	    for(int i=1;i<=len;i++)ans.mat[i][i]=1;
	    while(b.compareTo(BigInteger.ZERO)!=0){
	        if(b.mod(two).compareTo(BigInteger.ONE)==0)
	        	ans=MUL(ans,a);
	        a=MUL(a, a);
	        b=b.divide(two);
	    }
	    return ans;
	}

}
class Matrix{
	public  int mat[][]=new int[35][35];
	public Matrix(){
		for(int i=1;i<=32;i++){
			for(int j=1;j<=32;j++){
				mat[i][j]=0;
			}
		}
	}
	 })