BZOJ 1009 HNOI2008 GT考试 KMP+dp+矩阵快速幂-白红宇

BZOJ 1009 HNOI2008 GT考试 KMP+dp+矩阵快速幂

阅读量：5242 次

发布时间：2019-06-14

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

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1009

题意概述：

　　求有多少种方案构造一个长度为N的数字串，使得其中不包含给出的长度为M的数字串（数字串可以包含前导0），答案mod K。

　　N<=10^9,M<=20,K<=1000.

分析：

　　首先看到这个东西就想到了字符串+dp的套路......注意到N非常**大（滑稽）可能可以用矩阵快速幂优化一下。

　　那么构造一个线性的dp方程。

　　因为只有一个串，那么考虑用KMP来辅助dp。

　　令f(i,j)表示已经完成构造第i个字符，当前构造字符串和给出的串最长公共后缀前缀长度为j的方案数。

　　先考虑j!=0，有一种转移方案是f(i-1,j-1)，另外有转移方案为f(i-1,k)，满足S[j-1]是k的fail路径上第一个等于s[j-1]的数字。（因为公共前后缀长度为j的情况下当前字符是唯一确定的，所以所有的转移前面的系数为1）

　　然后考虑j=0，有一种转移是f(i-1,0)*9，另外有转移f(i-1,k)，前面的系数为k到0的fail路径上没有出现过的数字的数量。

　　请仔细体会这奥妙无穷的dp......（我要不要这么蠢啊...都不仔细想想...一遍就构造好的话哪里来的这么多事情）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #include
               
                11 #include
                
                 12 using namespace std;13 const int maxm=25;14 15 int N,M,K,f[maxm];16 char S[maxm];17 struct matrix{18 static const int maxn=22;19 int a[maxn][maxn],r,c;20 matrix(){ memset(a,0,sizeof(a)); r=c=0; }21 void init(int len){22 r=c=len;23 for(int i=0;i
                 
                  r); t=*this;37 for(int i=0;(1<
                  
                   <=y;i++){38 if((1<
                   
                    j-1){75 if(S[p]==S[j-1]) break;76 p=f[p];77 }78 if(p==j-1) A.a[i][j]=1;79 }80 }81 B.r=1,B.c=M;82 B.a[0][0]=9,B.a[0][1]=1;83 B=B*A.qkpow(N-1);84 int ans=0;85 for(int j=0;j

View Code

转载于:https://www.cnblogs.com/KKKorange/p/8743933.html

你可能感兴趣的文章