bzoj1009: [HNOI2008]GT考试-白红宇

bzoj1009: [HNOI2008]GT考试

阅读量：5278 次

发布时间：2019-06-14

本文共 948 字，大约阅读时间需要 3 分钟。

题解：

首先看到这道题n特别大，m很小，又有着很明显的状态转移，基本就可以看出这是一道矩阵优化dp题目了（终于不是在看完题解后再说了QAQ）

可以比较容易的看出状态转移，设f[i][j]表示长度为n的串匹配到了i，长度为m的串匹配到了j，预先处理m串的kmp，找到m串如何转移（我第一次写没有注意到需要处理kmp这回事，直接不符合的话转移到f[i][0]上，这样实际上是漏掉了情况）；

然后构造一个使f[i]转移到f[i+1]的矩阵B，使f[i]*B=f[i+1]；

然后用矩阵快速幂就行了；

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               11 #include
                
                 12 #include
                 
                  13 using namespace std;14 #define LL long long15 #define FILE "1"16 #define up(i,j,n) for(int i=j;i<=n;i++)17 #define down(i,n,j) for(int i=n;i>=j;i--)18 int n,m,k;19 const int maxn=30;20 char s[maxn];21 struct M{22 int v[maxn][maxn];23 M(){memset(v,0,sizeof(v));}24 friend M operator*(M a,M b){25 M c;26 for(int i=0;i

View Code

//这样的矩阵乘法时间复杂度很高，如果矩阵乘法的内容比较少还是自己写个比较好

转载于:https://www.cnblogs.com/chadinblog/p/5907165.html

你可能感兴趣的文章