此题如果直接利用递推关系，处理不好会超内存的。
首先找出递推关系式，先给出递推关系式：( L )=( L - 1 ) + ( L - 3 ) + ( L - 4 )；可以先尝试推导一下，推不出来再看下面的解释。
PS.以前做过一个类似的递推关系的题。
考虑当L=n时的情况，有两种情况：
①.如果最后一个字符为m ：此时，只要前面长度为n-1的串符合要求，则当前长度为n的串必然符合要求。
②.如果最后一个字符为f：此时，无法确定，因为可能存在不符合要求的串，继续分情况讨论
(1).最后倒数二个字符为f，仍然可能存在不符合要求的串，继续分情况讨论
1.倒数第三个字符为f,因为存在fff，所以该种情况必然不符合要求，舍去
2.倒数第三个字符为m，仍然有可能不符合要求，再分
a.最后第四个字符为f，存在fmf，所以该种情况必然不符合要求，舍去
b.最后第四个字符为m,只要前面长度为n-4的串符合要求，则当前长度为n的串必然也符合要求
(2).最后第二个字符为m，存在可能不符合要求的情况，分
1.最后第三个字符为f，存在fmf，此时必然不符合要求舍去
2.最后第三个字符为m，只要前面长度为n-3的串的情况符合要求，则当前长度为n的串必然符合要求。
所以讲符合要求的情况相加就得到：( L )=( L - 1 ) + ( L - 3 ) + ( L - 4 );
前面已经讲过如果只是用普通递归方法会超内存，所以这里要考虑优化。
怎么优化？先看下面的矩阵相乘的结果：
x矩阵是多少会得到后面的矩阵？我们只需考虑后面矩阵的第一行，因为其他元素为0.
第1行第1列的元素我们需要得到f ( n )，因为f(n)=f(n-1)+f(n-3)+f(n-4); 所以我们必须保留f(n-1)，f(n-3)，f(n-4) 所以与之相乘的数必须为1.
所以第1列元素可以确定，为1 0 1 1，注意，是第一列而不是第一行。
根据第一行第二列元素，我们可以确定x矩阵第二列元素：1 0 0 0.
根据第一行第三列元素，我们可以确定x矩阵第三列元素：0 1 0 0.
根据第一行第四列元素，我们可以确定x矩阵第四列元素：0 0 1 0.
所以x矩阵已经确定，所以我们可以得到下面的矩阵乘式：
所以，反复乘以x矩阵就可以得到想要的f(n);
所以可以先求出x矩阵的L-4(不是L)次方，到这就转化为了矩阵快速幂问题。然后在用 f(4) f(3) f(2) f(1) 乘以求次方后的矩阵的第一列元素 ，相加就得到f(n)=res[0][0]*f[4]+res[1][0]*f[3]+res[2][0]*f[2]+res[3[0]*f[1]。
#include<iostream>
#include<cstring>
#include<string>
#define maxn 5
using namespace std;
struct mat{
int a[maxn][maxn];
};
mat mat_mul(mat x,mat y,int Mod){
mat ans;
memset(ans.a,,sizeof(ans.a));
for (int i=;i<;i++)
for (int j=;j<;j++)
for (int k=;k<;k++){
ans.a[i][j]+=x.a[i][k]*y.a[k][j];
ans.a[i][j]%=Mod;
}
return ans;
}
void mat_pow(mat &res,int k,int Mod){ //res的k次方
mat c=res;
k--;
while (k){
if (k&) res=mat_mul(res,c,Mod);
k>>=;
c=mat_mul(c,c,Mod);
}
}
int main(){
int l,m;
while (cin >> l >> m){
int f[]={};
f[]=;f[]=;f[]=;f[]=;
mat res;
memset(res.a,,sizeof(res.a));
res.a[][]=res.a[][]=res.a[][]=res.a[][]=res.a[][]=res.a[][]=;
if (l<=){
cout << f[l]%m << endl;
continue;
}
else mat_pow(res,l-,m);
int ans=;
for (int i=;i<;i++){
ans+=res.a[i][]*f[-i]%m;
}
cout << ans%m << endl;
}
}