233
题目：题意：分析：代码：
题目：
传送门
题意：
对于一个
4
∗
n
4*n
4∗n的矩阵，求用
1
∗
2
1*2
1∗2的小矩阵将其恰好填满的方案数
分析：
O
E
I
S
大
法
好
OEIS大法好
OEIS大法好 这个不解释，谁用谁说好
a
[
i
]
=
a
[
i
−
1
]
+
a
[
i
−
2
]
∗
5
+
a
[
i
−
3
]
−
a
[
4
]
a[i]=a[i-1]+a[i-2]*5+a[i-3]-a[4]
a[i]=a[i−1]+a[i−2]∗5+a[i−3]−a[4] 然后对于这个式子用矩阵乘法进行优化
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
#define LZXANDME 1314
inline LL
read() {
LL d
=0,f
=1;char s
=getchar();
while(s
<'0'||s
>'9'){if(s
=='-')f
=-1;s
=getchar();}
while(s
>='0'&&s
<='9'){d
=d
*10+s
-'0';s
=getchar();}
return d
*f
;
}
using namespace std
;
LL n
,LZX
;
const LL s
[5][5]=
{
{0,0,0,0,0},
{0,1,5,1,-1},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0}
};
LL f
[5],x
[5][5];
void mul()
{
LL e
[5];memset(e
,0,sizeof(e
));
for(LL i
=1;i
<=4;i
++)
for(LL j
=1;j
<=4;j
++)
(e
[i
]+=f
[j
]*x
[i
][j
])%=LZX
;
memcpy(f
,e
,sizeof(e
));
return;
}
void mulself()
{
LL e
[5][5];memset(e
,0,sizeof(e
));
for(LL i
=1;i
<=4;i
++)
for(LL j
=1;j
<=4;j
++)
for(LL k
=1;k
<=4;k
++)
(e
[i
][j
]+=x
[i
][k
]*x
[k
][j
])%=LZX
;
memcpy(x
,e
,sizeof(e
));
return;
}
int main()
{
while(1)
{
n
=read();LZX
=read();
if (n
==1) {printf("1\n"); continue;}
if (n
==2) {printf("5\n"); continue;}
if (n
==3) {printf("11\n"); continue;}
if (n
==4) {printf("36\n"); continue;}
if(!n
&&!LZX
) break;
f
[4]=1%LZX
;f
[3]=5%LZX
;f
[2]=11%LZX
;f
[1]=36%LZX
;
memcpy(x
,s
,sizeof(s
));
n
-=4;
while(n
)
{
if(n
&1) mul();
mulself();
n
>>=1;
}
printf("%lld\n",(f
[1]%LZX
+LZX
)%LZX
);
}
return 0;
}
