给你n个人，排成一个长度是n的队伍，人只有两类f,m，问可以有多少种排法使度列中不出现fff，fmf这样的子串。
思路：
一开始暴力，结果超时了，其实这个题目要是能找到类似于斐波那契那样的公式，就可以瞬间用矩阵乘法+快速幂秒掉大数据，现在我们来找公式，我们现在来讨论当前队列的最后一个字母，如果是m那么之前的所有+m都不会冲突，所以有f(n-1)个，如果是f呢？，这个时候我们要考虑不可以出现fff,fmf这样的序列，那么新形成的后缀也就只有mmf，mff可以满足了，mmf前面是什么都可以满足，所以f(n - 3),而mff还得往前找，只有mmff前面是什么都可以，这时是f(n - 4),所以最终 f(n) = f(n - 1) + f(n - 3) + f(n - 4),接下来就构造矩阵，矩阵的构造也很简单，但是构造的时候别忘了，矩阵没有交换律的。
f(x)f(x+1)f(x+2)f(x+3) * [ 0 0 0 1 ] = f(x+1)f(x+2)f(x+3)f(x+4)
[ 1 0 0 1 ]
[ 0 1 0 0 ]
[ 0 0 1 1 ]
构造完矩阵就可以用矩阵快速幂吊打这道题了。
#include<stdio.h> #include<string.h> int MOD; typedef struct { int mat[5][5]; }A; A mat_mat(A a ,A b) { A c; memset(c.mat ,0 ,sizeof(c.mat)); for(int k = 1 ;k <= 4 ;k ++) for(int i = 1 ;i <= 4 ;i ++) if(a.mat[i][k]) for(int j = 1 ;j <= 4 ;j ++) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD; return c; } A quick_mat(A a ,int b) { A c; memset(c.mat ,0 ,sizeof(c.mat)); for(int i = 1 ;i <= 4 ;i ++) c.mat[i][i] = 1; while(b) { if(b & 1) c = mat_mat(c ,a); a = mat_mat(a ,a); b >>= 1; } return c; } int main () { A a ,b; int n ,num[5]; memset(a.mat ,0 ,sizeof(a.mat)); a.mat[1][4] = a.mat[2][1] = a.mat[2][4] = 1; a.mat[3][2] = a.mat[4][3] = a.mat[4][4] = 1; num[0] = 1 ,num[1] = 2 ,num[2] = 4 ,num[3] = 6; while(~scanf("%d %d" ,&n ,&MOD)) { if(n <= 3) { printf("%d " ,num[n] % MOD); continue; } b = quick_mat(a ,n - 3); int ans = num[0] * b.mat[1][4] + num[1] * b.mat[2][4] + num[2] * b.mat[3][4] + num[3] * b.mat[4][4]; printf("%d " ,ans % MOD); } return 0; }