D
e
s
c
r
i
p
t
i
o
n
Description
Description
求用
1
×
2
1\times 2
1×2的方块覆盖
4
×
n
4\times n
4×n的而方案数，答案对
m
o
d
mod
mod取模
数据范围： 30%，
n
≤
8
n\leq 8
n≤8 60%，
n
≤
1
0
6
n\leq 10^6
n≤106 100%，
n
≤
1
0
9
n\leq 10^9
n≤109
S
o
l
u
t
i
o
n
Solution
Solution
观察题目发现，这道题就是缩小了矩阵的规模但增大了宽度后的麦当劳的梦想
然后有两种破题路径
O
(
n
)
O(n)
O(n)通项公式
C
o
d
e
Code
Code
#include<cstdio>
#include<cctype>
using namespace std
;int n
,mod
;
long long f
[1000011];
inline long long read()
{
char c
;int d
=1;long long f
=0;
while(c
=getchar(),!isdigit(c
))if(c
==45)d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
signed main()
{
while(n
=read(),mod
=read(),n
||mod
)
{
f
[1]=0;f
[2]=f
[3]=1;f
[4]=5;
for(register int i
=5;i
<=n
+2;i
++) f
[i
]=(f
[i
-1]+5*f
[i
-2]%mod
+f
[i
-3]-f
[i
-4]+mod
)%mod
;
printf("%d\n",f
[n
+2]%mod
);
}
}
O
(
m
3
l
o
g
n
)
=
O
(
64
l
o
g
n
)
≈
O
(
l
o
g
n
)
C
o
d
e
O(m^3logn)=O(64logn)\approx O(logn)Code
O(m3logn)=O(64logn)≈O(logn)Code
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std
;int n
,mod
;
struct node
{long long a
[5][5];}x
,ans
;
inline node
mul(node x
,node y
)
{
node z
;
memset(&z
,0,sizeof(z
));
for(register int i
=0;i
<5;i
++)
for(register int j
=0;j
<5;j
++)
for(register int k
=0;k
<5;k
++)
z
.a
[i
][j
]=(z
.a
[i
][j
]%mod
+(long long)x
.a
[i
][k
]*y
.a
[k
][j
]%mod
+mod
)%mod
;
return z
;
}
inline long long read()
{
char c
;int d
=1;long long f
=0;
while(c
=getchar(),!isdigit(c
))if(c
==45)d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
signed main()
{
node yb
=(node
){{
{1,1,0,0,0},
{5,0,1,0,0},
{1,0,0,1,0},
{-1,0,0,0,1},
{0,0,0,0,0}
}};
while(n
=read(),mod
=read(),n
||mod
)
{
n
+=2;
ans
.a
[0][0]=11%mod
;ans
.a
[0][1]=5%mod
;ans
.a
[0][2]=1%mod
;ans
.a
[0][3]=1%mod
;ans
.a
[0][4]=0;
if(n
<=5)
{
printf("%lld\n",ans
.a
[0][5-n
]);
continue;
}
n
-=5;x
=yb
;
while(n
)
{
if(n
&1) ans
=mul(ans
,x
);
x
=mul(x
,x
);
n
>>=1;
}
printf("%lld\n",ans
.a
[0][0]);
}
}
