题目的大意是：给定1*2的小矩形，去拼接一个4*n（n<10^9）的矩形，问有多少种方案。
Quad Tiling
Description
Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:
In how many ways can you tile a 4 × N (1 ≤ N ≤ 109) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 105).
Input
Input consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.
Output
For each test case, output the answer modules M.
Sample Input
1 10000 3 10000 5 10000 0 0
Sample Output
1 11 95
导出递推式：f(n) = f(n-1)+4*f(n-2)+2f(n-3)+3f(n-4)+...+2*f(n-i)+3*f(n-i-1)+...//i为奇数，i+1为偶数。
所以 f(n-2) = f(n-3+4f(n-4)+2f(n-5)+3f(n-6)+...+2f(n-i)+3f(n-i-1)+...//把n换成n-2.
所以 f(n-2)+f(n-3)-f(n-4) = 2f(n-3)+3f(n-4)+...+2f(n-i)+3f(n-i-1)+...
所以 f(n) = f(n-1)+5f(n-2)+f(n-3)-f(n-4);
#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <algorithm> #include <queue> #include <map> using namespace std; #define MAXN 4 #define MAXM 4 int Mod; struct Matrix { int n, m; int a[MAXN][MAXM]; Matrix(int n_, int m_) { n = n_; m = m_; } /*Matrix operator + (const Matrix &b) const{ Matrix tmp(n, m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j] = a[i][j] + b.a[i][j]; return tmp; } Matrix operator - (const Matrix &b) const{ Matrix tmp(n, m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j] = a[i][j]-b.a[i][j]; return tmp; }*/ Matrix operator * (const Matrix &b) const{ Matrix tmp(n, b.m); memset(tmp.a, 0, sizeof(tmp.a)); for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) for(int k=0; k<m; k++) tmp.a[i][j] = (tmp.a[i][j]+a[i][k]*b.a[k][j]) % Mod; return tmp; } }; Matrix operator ^ (Matrix a, int p) { Matrix tmp(a.n, a.m); memset(tmp.a, 0, sizeof(tmp.a)); for(int i=0; i<a.n && i<a.m; i++) tmp.a[i][i]=1; while(p) { if(p & 1) tmp = tmp*a; a = a*a; p = p >> 1; } return tmp; } int main() { freopen("poj3420.in", "r", stdin); freopen("poj3420.out", "w", stdout); int n; while ( scanf("%d%d", &n, &Mod) && n && Mod) { Matrix A(4, 4); A.a[0][0]=0; A.a[0][1]=1; A.a[0][2]=0; A.a[0][3]=0; A.a[1][0]=0; A.a[1][1]=0; A.a[1][2]=1; A.a[1][3]=0; A.a[2][0]=0; A.a[2][1]=0; A.a[2][2]=0; A.a[2][3]=1; A.a[3][0]=-1;A.a[3][1]=1; A.a[3][2]=5; A.a[3][3]=1; Matrix h(4,4); h.a[0][0]=1; h.a[1][0]=5; h.a[2][0]=11; h.a[3][0]=36; A = A ^ (n-1); A = A * h; printf("%d\n", A.a[0][0]); } return 0; }
原文：http://www.cnblogs.com/ygcguoguo/p/3529600.html