题目
解题思路
一开始用状态压缩做，只有60分，后来改成了矩阵乘法。 但是这个规律很难找到，不过也因此学会了一种新的方法。 即:
f
[
i
]
=
f
[
i
−
1
]
∗
1
+
f
[
i
−
2
]
∗
5
+
f
[
i
−
3
]
∗
1
+
f
[
i
−
4
]
∗
−
1
f[i]=f[i-1]*1+f[i-2]*5+f[i-3]*1+f[i-4]*-1
f[i]=f[i−1]∗1+f[i−2]∗5+f[i−3]∗1+f[i−4]∗−1
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define rep(i,x,y) for (register int i=x;i<=y;i++)
using namespace std
;
int n
,lw
;
long long f
[7][7],a
[7][7],m
[7][7];
void mull(){
memset(m
,0,sizeof(m
));
rep(i
,1,4) rep(j
,1,4) rep(k
,1,4) m
[i
][j
]=(m
[i
][j
]+f
[k
][j
]*f
[i
][k
]+lw
)%lw
;
memcpy(f
,m
,sizeof(m
));
}
void mul(){
memset(m
,0,sizeof(m
));
rep(i
,1,4) rep(j
,1,4) rep(k
,1,4) m
[i
][j
]=(m
[i
][j
]+a
[k
][j
]*f
[i
][k
]+lw
)%lw
;
memcpy(a
,m
,sizeof(m
));
}
int main(){
while (cin
>>n
>>lw
&&n
){
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{
memset(a
,0,sizeof(a
));
memset(f
,0,sizeof(f
));
a
[1][1]=36,a
[2][1]=11,a
[3][1]=5,a
[4][1]=1;
f
[2][1]=1,f
[3][2]=1,f
[4][3]=1,f
[1][1]=1,f
[1][2]=5,f
[1][3]=1,f
[1][4]=-1;
for (int i
=n
-4;i
;i
>>=1,mull()) if (i
&1) mul();
cout
<<a
[1][1]%lw
<<endl
;
}
}
}
