题目链接：

题目大意：

n个人排队，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列为O队列，否则为E队列，有多少个序列为E队列。

解题思路：

用f(n)表示n个人满足条件的结果，那么如果最后一个人是m的话，那么前n-1个满足条件即可，就是f(n-1)； 

如果最后一个是f那么这个还无法推出结果，那么往前再考虑一位：那么后三位可能是：mmf, fmf, mff, fff，其中fff和fmf不满足题意所以我们不考虑，但是如果是 

mmf的话那么前n-3可以找满足条件的即：f(n-3)；如果是mff的话，再往前考虑一位的话只有mmff满足条件即：f(n-4) 

所以f(n)=f(n-1)+f(n-3)+f(n-4)，递推会超时，可用矩阵快速幂 

构造一个矩阵： 

1 #include
     
       2 using namespace std; 3 int MOD; 4 struct Mat 5 { 6     int a[4][4]; 7     int n, m;//n为行数，m为列数 8     Mat(int n, int m):n(n), m(m) 9     {10         memset(a, 0, sizeof(a));11     }12     void init()13     {14         for(int i = 0; i < n; i++)a[i][i] = 1;//初始化成单位矩阵15     }16     void output()17     {18         for(int i = 0; i < n; i++)19         {20             for(int j = 0; j < m; j++)21             {22                 cout<
      
       <<" ";23             }24             cout<
       
        > n >> k)74     {75         MOD = k;76         if(n <= 4)77         {78             cout<
        
         <