题解:构建Trie图
由图可知，设f(n)为字符串长度为n时复合条件的字符串个数，以字符串最后一个字符为分界点，当最后一个字符为m时前n-1个字符没有限制，即为f(n-1)；当最后一个字符为f时就必须去除最后3个字符是fmf和fff的情况,在考虑最后两个字符为mf和ff的情况，显然不行；最后3个字符为fmf、mmf和fff、mff时只有当最后3个字符为mmf时前n-3个字符没有限制，即为f(n-3)，当为mff时第n-3个字符可能为f因而对前n-3个字符串有限制；最后4个字符为fmff和mmff时mmff可行。得到公式f(n)=f(n-1)+f(n-3)+f(n-4)
然后，构建矩阵进行幂运算即可。
/*matrix a={ {0,1,0,0}, {0,0,1,0}, {0,0,0,1}, {1,1,0,1}, }; */ #include <cstdio> #include <iostream> #define maxn 4 #define rep(i,n) for(int i=0;i<n;i++) using namespace std; struct matrix { int v[maxn][maxn]; void init() { memset(v,0,sizeof v); } }a,b; matrix mul(matrix a,matrix b,int l,int m,int n,int mod) { matrix c; c.init(); rep(i,l)rep(j,m)rep(k,n)c.v[i][j]=(c.v[i][j]+(a.v[i][k]*b.v[k][j])%mod)%mod; return c; } matrix power(matrix a,int l,int m,int n,int x,int mod) { if(x==1)return a; matrix tmp=power(a,l,m,n,x>>1,mod); tmp=mul(tmp,tmp,l,m,n,mod); if(x&1)tmp=mul(tmp,a,l,m,n,mod); return tmp; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { a.init(); b.init(); a.v[0][1]=1;a.v[1][2]=1; a.v[2][3]=1;a.v[3][0]=1; a.v[3][1]=1;a.v[3][3]=1; b.v[0][0]=1;b.v[1][0]=2; b.v[2][0]=4;b.v[3][0]=6; a=power(a,4,4,4,n,m); a=mul(a,b,4,1,4,m); printf("%d\n",a.v[0][0]); } return 0; }