本文主要是介绍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
/*
解题报告：1.题意：求在一个4*N（N<=1000000000）的格子中放1*2的格子的方案数。
2.可以推出公式：F(n)=F(n-1)+5*F(n-2)+F(n-3)-F(n-4).像处理斐波
那契数列一样，利用矩阵进行优化。
F(1) = 1, F(2) = 5, F(3) = 11, F(4) = 36.
|F(n) | |1 5 1 -1| |F(n-1)||F(n-1)| = |0 1 0 0|*|F(n-2)||F(n-2)| |0 0 1 0| |F(n-3)||F(n-3)| |0 0 0 1| |F(n-4)||F(n-3)| |0 0 0 1| |F(n-4)|-> |F(n-2)| = |0 0 1 0|*|F(n-3)||F(n-1)| |0 1 0 0| |F(n-2)||F(n) | |1 5 1 -1| |F(n-1)|
*/
//标程：#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n, m; const int c = 4; int N, Mod; struct Matrix {int n, m;int a[c][c];Matrix() { }Matrix(int nn,int mm) : n(nn), m(mm) {};void clear(){n = m = 0;memset(a,0,sizeof(a));}Matrix operator + (const Matrix &b) const {Matrix temp = Matrix(n,m);temp.n = n, temp.m = m;for(int i = 0; i < n; ++ i)for(int j = 0; j < m; ++ j)temp.a[i][j] = a[i][j] + b.a[i][j];return temp;}Matrix operator - (const Matrix &b) const {Matrix temp = Matrix(n,m);temp.n = n, temp.m = m;for(int i = 0; i < n; ++ i)for(int j = 0; j < m; ++ j)temp.a[i][j] = a[i][j] - b.a[i][j];return temp;}Matrix operator * (const Matrix &b) const {Matrix temp = Matrix(n,m);temp.clear();temp.n = n, temp.m = m;for(int i = 0; i < n; ++ i)for(int j = 0; j < b.m; ++ j)for(int k = 0; k < m; ++ k){temp.a[i][j] += a[i][k] * b.a[k][j];temp.a[i][j] %= Mod;}return temp;} }f, d; Matrix operator ^ (Matrix a,int p) {Matrix ret = Matrix(a.n,a.m);for(int i = 0; i < a.n; i ++)for(int j = 0; j < a.m; j ++)ret.a[i][j] = (i == j ? 1 : 0);while(p){if(p % 2) ret = ret * a;a = a * a;p /= 2;}return ret; } int main() { // freopen("a.txt","r",stdin);while(scanf("%d%d",&N,&Mod), n + Mod){ d = Matrix(4,4);d.a[0][0] = 1, d.a[1][0] = 5;d.a[2][0] = 11, d.a[3][0] = 36;f = Matrix(4,4);f.a[0][0]=0, f.a[0][1]=1, f.a[0][2]=0, f.a[0][3]=0;f.a[1][0]=0, f.a[1][1]=0, f.a[1][2]=1, f.a[1][3]=0;f.a[2][0]=0, f.a[2][1]=0, f.a[2][2]=0, f.a[2][3]=1;f.a[3][0]=-1, f.a[3][1]=1, f.a[3][2]=5, f.a[3][3]=1;f = f ^ (N-1);f = f * d;printf("%d\n",f.a[0][0]);}return 0; }
这篇关于Quad Tiling的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
