POJ3420-Quad Tiling

Quad Tiling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4495		Accepted: 2050

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 ≤ 10⁹) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 10⁵).

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

Source

POJ Monthly--2007.10.06, Dagger

题意：将4*N的地板用2*1的瓷砖铺满，问一共有多少方案数

解题思路：把4当作列数，n当作行数。当第n行填满时，第(n+1)行会出现以下几种情况：

情况a为第n行刚好填满且没有突出到第(n + 1)行，即为所求答案，由图不难推出：
a[n] = a[n - 1] + b[n - 1] + c[n - 1] + dx[n - 1] + dy[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
dx[n] = a[n - 1] + dy[n - 1]
dy[n] = a[n - 1] + dx[n - 1]
e[n] = c[n - 1]
令d[n] = dx[n] + dy[n]
则 a[n] = a[n - 1] + b[n - 1] + c[n - 1] + d[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
d[n] = a[n - 1] * 2 + d[n - 1]
e[n] = c[n - 1]

根据这个构造出矩阵即可

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

int n;
LL mod;

struct Matrix
{
	LL v[10][10];
	Matrix()
	{
		memset(v, 0, sizeof v);
	}
} dan;

Matrix mul(Matrix a, Matrix b, int d)
{
	Matrix ans;
	for (int i = 0; i < d; i++)
		for (int j = 0; j < d; j++)
			for (int k = 0; k < d; k++)
				ans.v[i][j] =(ans.v[i][j]+ a.v[i][k] * b.v[k][j]%mod)%mod;
	return ans;
}

Matrix pow(Matrix a, int k, int d)
{
	Matrix ans = dan;
	while (k)
	{
		if (k & 1) ans = mul(ans, a, d);
		k >>= 1;
		a = mul(a, a, d);
	}
	return ans;
}

int main()
{
	while (~scanf("%d%lld", &n, &mod) && (n + mod))
	{
		dan.v[0][0] = dan.v[0][1] =dan.v[0][2]=1;
		dan.v[0][3] = 2;
		Matrix a, ans;
		a.v[0][0] = a.v[0][1] = a.v[0][2] = 1, a.v[0][3] = 2;
		a.v[1][0] = 1;
		a.v[2][0] = a.v[2][4] = 1;
		a.v[3][0] = a.v[3][3] = 1;
		a.v[4][2] = 1;
		ans = pow(a, n - 1, 5);
		printf("%lld\n", ans.v[0][0]%mod);
	}
	return 0;
}