给你一个长度为L的由m和f两种字母组成的字符串，定义存在fmf以及fff子串的都是不符合要求的串，问长度为L的符合要求的串有多少个
那么当L=1,时，dp[1]=1,L=2时，dp[2]=4,L=3时，dp[3]=6
考虑当L=n时的情况，将原问题拆分为两个子问题
1.最后一个字符为m 。此时，只要前面长度为n-1的串符合要求，则当前长度为n串必然符合要求。
2.最后一个字符为f。此时，存在可能不符合要求的串，继续分情况讨论
2(1)，最后第二个字符为f，仍然存在可能不符合要求的串，继续分
2(1)(1),最后第三个字符为f,该种情况必然不符合要求，舍去
2(1)(2),最后第三个字符为m，仍然有可能不符合要求，再分
2(1)(2)(1),最后第四个字符为f，该种情况必然不符合要求，舍去
2(1)(2)(2),最后第四个字符为m,只要后面长度为n-4的串符合要求，则当前长度为n的串必然也符合要求
2(2)，最后第二个字符为m，存在可能不符合要求的情况，分
2(2)(1),最后第三个字符为f，此时必然不符合要求舍去
2(2)(2),最后第三个字符为m，只要后面长度为n-3的串符合要求，则当前长度为n的串必然符合要求。
综上，设(a@n)为长度为n时符合情况的串，
则组合(a@n-1)m
(a@n-4)mmff
(a@n-3)mmf 是唯一三种可能的情况
因此我们有递推式f(n)=f(n-1)+f(n-3)+f(n-4)
#include<iostream>
using namespace std;
int DP[1000001][31];
int main(){
int l,m;
for(int i=1;i<=31;i++){
DP[0][i]=1%i;
DP[1][i]=2%i;
DP[2][i]=4%i;
DP[3][i]=6%i;
}
for(int i=4;i<=1000001;i++){
for(int j=1;j<=31;j++){
DP[i][j]=(DP[i-1][j]+DP[i-3][j]+DP[i-4][j])%j;
}
}
while(cin>>l>>m)
cout<<DP[l][m]<<endl;;
return 0;
}
发现空间爆了。。
不能保存所有的，只能一个个算。。用矩阵快速幂+取模
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int l,m;
while(cin>>l>>m){
int tmp[4][4]={1,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0};
int a[4][4]={1,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0};
int b[4][4]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int ans[4][4]={1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1};
int answer;
if(l==0)
answer=1;
else if(l==1)
answer=2;
else if(l==2)
answer=4;
else if(l==3)
answer=6;
else if(l==4)
answer=9;
else{
for(l=l-4;l;l>>=1){
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
a[i][j]=tmp[i][j];
}
}
if(l%2==1){
memset(b,0,sizeof(b));
for(int k=0;k<=3;k++){
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
b[i][j]=(b[i][j]+ans[i][k]*tmp[k][j])%m;
}
}
}
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
ans[i][j]=b[i][j];
}
}
}
memset(tmp,0,sizeof(tmp));
for(int k=0;k<=3;k++){
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
tmp[i][j]=(tmp[i][j]+a[i][k]*a[k][j])%m;
}
}
}
}
answer=(9*ans[0][0]+6*ans[0][1]+4*ans[0][2]+2*ans[0][3])%m;
}
cout<<answer%m<<endl;
}
return 0;
}