[
L
i
n
k
\frak{Link}
Link] [
S
o
l
u
t
i
o
n
\frak{Solution}
Solution]
棋盘覆盖。 首先列出状态压缩的方程式。规律对于每一列相同，可以用矩阵加速转移。 注意到里面只有几种是有效状态。
1234
000011110011110010010110
其中，第三和第四种状态本质上是相同的。 所以实际上只有五种状态。用这五种状态列出转移式子用矩阵转移即可。 矩阵如下。
1, 1, 1, 1, 0. 1, 0, 0, 0, 0. 2, 0, 1, 0, 0. 1, 0, 0, 0, 1. 0, 0, 0, 1, 0.
#Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<cstdlib>
using namespace std
;
int T
;
long long N
,M
,tmp
[5][5]={};
long long transfer
[5][5]={{1,1,1,1,0},{1,0,0,0,0},{2,0,1,0,0},{1,0,0,0,1},{0,0,0,1,0}};
long long qmpow(long long t
)
{
long long ans
[5][5]={{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
long long base
[5][5],ret
=0;
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
base
[i
][j
]=transfer
[i
][j
];
}
}
while(t
)
{
if(t
&1)
{
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
tmp
[i
][j
]=0;
}
}
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
for(int k
=0;k
<5;++k
)
{
tmp
[i
][j
]=(tmp
[i
][j
]+ans
[i
][k
]*base
[k
][j
]%M
)%M
;
}
}
}
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
ans
[i
][j
]=tmp
[i
][j
];
}
}
}
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
tmp
[i
][j
]=0;
}
}
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
for(int k
=0;k
<5;++k
)
{
tmp
[i
][j
]=(tmp
[i
][j
]+base
[i
][k
]*base
[k
][j
]%M
)%M
;
}
}
}
for(int i
=0;i
<5;++i
)
{
for(int j
=0;j
<5;++j
)
{
base
[i
][j
]=tmp
[i
][j
];
}
}
t
>>=1;
}
ret
=(ret
+5ll*ans
[0][0]%M
)%M
;
ret
=(ret
+1ll*ans
[1][0]%M
)%M
;
ret
=(ret
+2ll*ans
[2][0]%M
)%M
;
ret
=(ret
+1ll*ans
[3][0]%M
)%M
;
ret
=(ret
+1ll*ans
[4][0]%M
)%M
;
return ret
;
}
int main()
{
while(~scanf("%lld%lld",&N
,&M
))
{
if(N
==0)return 0;
if(N
==1ll)
{
printf("%lld\n",1ll%M
);
continue;
}
if(N
==2ll)
{
printf("%lld\n",5ll%M
);
continue;
}
printf("%lld\n",qmpow(N
-2ll));
}
return 0;
}
另外也可以手模构造4 x 4转移矩阵。
