题意
求出用
2
×
1
2\times 1
2×1的牌填满
4
×
N
4\times N
4×N的矩形方案数%
M
M
M。
思路
可以打表，得出
1
,
5
,
11
,
36
,
95
1,5,11,36,95
1,5,11,36,95，之后代入
O
E
I
S
OEIS
OEIS，得出递推公式（逃
a
(
n
)
=
a
(
n
−
1
)
+
5
∗
a
(
n
−
2
)
+
a
(
n
−
3
)
−
a
(
n
−
4
)
a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4)
a(n)=a(n−1)+5∗a(n−2)+a(n−3)−a(n−4) 矩阵乘法加速递推即可。
代码
#include<cstdio>
#include<cstring>
int n
, m
;
struct matrix
{
int a
[5][5];
};
matrix
operator *(matrix
&a
, matrix
&b
){
matrix c
;
memset(c
.a
, 0, sizeof(c
.a
));
for (int i
= 1; i
<= 4; i
++)
for (int j
= 1; j
<= 4; j
++)
for (int k
= 1; k
<= 4; k
++)
c
.a
[i
][j
] = (c
.a
[i
][j
] + (long long)a
.a
[i
][k
] * b
.a
[k
][j
]) % m
;
return c
;
}
void power(int b
) {
matrix A
;
memset(A
.a
, 0, sizeof(A
.a
));
A
.a
[1][4] = -1;
A
.a
[2][1] = 1;
A
.a
[2][4] = 1;
A
.a
[3][2] = 1;
A
.a
[3][4] = 5;
A
.a
[4][3] = 1;
A
.a
[4][4] = 1;
matrix r
;
r
.a
[1][1] = 1;
r
.a
[1][2] = 5;
r
.a
[1][3] = 11;
r
.a
[1][4] = 36;
for (; b
; b
>>= 1) {
if (b
& 1) r
= r
* A
;
A
= A
* A
;
}
printf("%d\n", r
.a
[1][4]);
}
int main() {
while (scanf("%d %d", &n
, &m
), n
|| m
) {
if (n
== 1) printf("1\n");
else if (n
== 2) printf("5\n");
else if (n
== 3) printf("11\n");
else if (n
== 4) printf("36\n");
else if (n
== 5) printf("95\n");
else power(n
- 4);
}
}
