POJ3420QuadTiling【矩阵快速幂】

Quad Tiling

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 5008 Accepted: 2269

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

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

问题链接：POJ3420 Quad Tiling

问题简述：（略）

问题分析：

    递推式如下：

a[0]=1，a[1]=1，a[2]=5，a[3]=11，

a[n]=a[n-1]+5a[n-2]+a[n-3]-an-4

    采用矩阵快速模幂计算，模板题。关键是找到那个递推式。

程序说明：（略）

参考链接：（略）

题记：（略）

AC的C++语言程序如下：

/* POJ3420 Quad Tiling */
#include
#include
using namespace std;
const int N = 10;
const int M = 10;
int r, mod;
struct Matrix
{
int n,m;
int a[N][M];
void clear()
{
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator +(const Matrix &b) const
{
Matrix c;
c.n = n;
c.m = m;
for(int i = 0; i for(int j = 0; j c.a[i][j] = a[i][j] + b.a[i][j];
return c;
}
Matrix operator -(const Matrix &b) const
{
Matrix c;
c.n = n;
c.m = m;
for(int i = 0; i for(int j = 0; j c.a[i][j] = a[i][j] - b.a[i][j];
return c;
}
Matrix operator *(const Matrix &b) const
{
Matrix c;
c.clear();
c.n = n;
c.m = b.m;
for(int i = 0; i for(int j = 0; j for(int k = 0; k {
c.a[i][j] += a[i][k] * b.a[k][j];
c.a[i][j] %= mod;
}
return c;
}
Matrix powermod(int x)
{
Matrix c;
c.clear();
c.n = c.m = n;
for(int i = 0; i c.a[i][i] = 1;
if(x == 0)
return c;
else if(x == 1)
return *this;
Matrix d = powermod(x / 2);
d = d * d;
if(x % 2 )
d = d * (*this);
return d;
}
};
int main()
{
while(scanf("%d%d", &r, &mod) == 2 && (r || mod)) {
int a[] = {1, 1, 5, 11};
if(r <= 3) {
printf("%d\n", a[r] % mod);
continue;
}
Matrix b;
b.clear();
b.n = b.m = 4;
b.a[0][1] = b.a[1][2] = b.a[2][3] = 1;
b.a[3][0] = -1;
b.a[3][1] = 1;
b.a[3][2] = 5;
b.a[3][3] = 1;
b = b.powermod(r - 3);
Matrix x;
x.clear();
x.n = 4;
x.m = 1;
x.a[0][0] = 1;
x.a[1][0] = 1;
x.a[2][0] = 5;
x.a[3][0] = 11;
x = b * x;
printf("%d\n",(x.a[3][0] + mod) % mod);
}
return 0;
}