hdu2604 矩阵快速幂

63 阅读 0 评论 42 点赞

我是靠谱客的博主秀丽耳机，最近开发中收集的这篇文章主要介绍hdu2604 矩阵快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
给你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("%dn" ,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("%dn" ,ans % MOD);
   }
   return 0;
}