正题
题目大意
求
1
×
2
1\times 2
1×2的方块铺满
4
×
n
4\times n
4×n的方格方案总数。
解题思路
首先 当计算
f
n
f_n
fn时， 显然最后一排可以
(
−
−
−
−
)
(
∣
∣
∣
∣
)
(
−
−
∣
∣
)
(
∣
−
−
∣
)
(
∣
∣
−
−
)
(--\ --)(|\ \ |\ \ |\ \ |)(--\ \ |\ \ |)(|\ \ --\ \ |)(|\ \ |--)
(−− −−)(∣ ∣ ∣ ∣)(−− ∣ ∣)(∣ −− ∣)(∣ ∣−−)
然后第一种显然方案数是
f
n
−
1
f_{n-1}
fn−1 第二种显然是
f
n
−
2
f_{n-2}
fn−2 主要是后三种是一样的:
(
∣
∣
−
−
)
(|\ \ |--)
(∣ ∣−−)或
(
∣
∣
∣
∣
)
(|\ \ |\ \ |\ \ |)
(∣ ∣ ∣ ∣)
(
∣
∣
−
−
)
(|\ \ |--)
(∣ ∣−−)或
(
∣
∣
−
−
)
(|\ \ |--)
(∣ ∣−−) 继续往后推会发现其实最后答案
∑
i
=
1
n
−
2
f
i
\sum_{i=1}^{n-2} f_{i}
∑i=1n−2fi
那么答案就变成了
4
∗
f
n
−
2
+
f
n
−
3
−
f
n
−
4
4*f_{n-2}+f_{n-3}-f_{n-4}
4∗fn−2+fn−3−fn−4 然后和前面两种加起来就是
f
n
=
f
n
−
1
+
5
∗
f
n
−
2
+
f
n
−
3
−
f
n
−
4
f_{n}=f_{n-1}+5*f_{n-2}+f_{n-3}-f_{n-4}
fn=fn−1+5∗fn−2+fn−3−fn−4
矩阵乘法加速即可
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std
;
const ll SIZE
=4;
ll n
,m
;
struct matrix
{
ll a
[SIZE
][SIZE
];
}f
;
matrix
operator *(matrix
&a
, matrix
&b
) {
matrix c
;
memset(c
.a
,0,sizeof(c
.a
));
for (ll i
=0;i
<SIZE
;i
++)
for (ll j
=0;j
<SIZE
;j
++)
for (ll k
=0;k
<SIZE
;k
++)
(c
.a
[i
][j
]+=a
.a
[i
][k
]*b
.a
[k
][j
])%=m
;
return c
;
}
void ycl()
{
memset(f
.a
,0,sizeof(f
.a
));
f
.a
[3][3]=1;f
.a
[3][2]=1;
f
.a
[2][3]=5;f
.a
[1][3]=1;
f
.a
[0][3]=-1;f
.a
[2][1]=1;
f
.a
[1][0]=1;
}
matrix
power(matrix f
,ll b
)
{
matrix ans
;
memset(ans
.a
,0,sizeof(ans
.a
));
ans
.a
[0][3]=ans
.a
[0][1]=ans
.a
[0][0]=1;
while(b
){
if(b
&1) ans
=ans
*f
;
f
=f
*f
;b
>>=1;
}
return ans
;
}
int main()
{
while(1)
{
scanf("%lld%lld",&n
,&m
);
if(!n
&&!m
) return 0;
ycl();
f
=power(f
,n
);
printf("%lld\n",(f
.a
[0][3]+m
)%m
);
}
}
