[关闭]
@Jerusalem 2015-11-12T17:30:15.000000Z 字数 1143 阅读 1639

HDU2243



  让我们考虑本题的一个弱化版本,即求出长度恰好为L的方案数。
  
  直接求解是non trival的,我们使用补集转化的思想,即求出长度为L的字符串,其任意位置对应的节点都不危险的方案数,再用26L减去其即可。
  
  则显然可以用f(i,j)代表目标串的第i位在AC自动机上对应编号为j的节点的方案数,且有f(i,j)=f(i1,k)×p(k,j)成立,其中p(i,j)代表AC自动机的第i个节点转移到第j个节点的方案数。这是trival的。关于这,可以参看POJ2778
  


  但事实上,我们的目标是求出Li=126iLi=1,notdanger(j)f(i,j),即求出Li=1,notdanger(j)f(i,j),令G表示初始矩阵,设t(i)=G×pi ,很容易发现f(i,j)=t(i)j,于是目标即是要求L1i=0totj=1,notdanger(j)t(i)j,将求和换序,即totj=1,notdanger(j)L1i=0t(i)j,即totj=1,notdanger(j)L1i=0t(i)
  
  让我们来观察t(i),事实上,这是一个关于p的多项式,即GL1i=1pi,由Horner's Rule,可以将pi 改写为[pi1]×p+E,于是构造矩阵R,其中的元素为两个矩阵:R=[pi1,E],构造转移矩阵T,元素为T1,1=p,T1,2=0,T2,1=E,T2,2=E,于是显然,t(i)=G([E,E]×TL1)1,1=GTL11,1
  
  这就完成了题目。
  


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注