題意：
? ? ? 給你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\n" ,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\n" ,ans % MOD);}return 0; }

總結

以上是生活随笔為你收集整理的hdu2604 矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。