HDOJ-2243 AC自动机.等比矩阵求和

HDOJ-2243 AC自动机.等比矩阵求和

题目是要说小于L长度的由小写字母组成的字符串有多少个包含所给的串...

从正方向想..要求出包含的..并且还要踢去重复包含的..又要加上被多踢的..整个一容斥问题了...但这题明显是不可行的...那么换个角度..先求出总共小于L的单词数(26^1+26^2+26^3+...26^L)..然后再减去不包括所给字符串的单词...相当于把每个单词看成POJ2778中的病毒...

但还有个问题...如何求出矩阵A的 A+A^2+A^3+....A^L .. 这里参考了​​    | A   E |         其中O代表O矩阵，E代表单位矩阵，这样，求出的K次矩阵的右上n子矩阵正好是       | O   E |         等比矩阵的K项和，这种构造法比我实现的两次二分快了4倍左右。

这里有个错误要注意...求出K次矩阵的右上子矩阵应该是K-1项的和...

Program:

#include#include#include#include#define ull unsigned __int64using namespace std; struct node1{ int son[26],fail; bool word;}point[205];struct node{ ull s[65][65];}temp,h,_2M[35],T; char s[7];queue myqueue;ull ans;int n,l,m;void Built_Trie(){ int i,len,h; memset(point[0].son,0,sizeof(point[0].son)); point[0].word=point[0].fail=0; m=0; while (n--) { scanf("%s",s); len=strlen(s); h=0; for (i=0;i=l) break; } memset(T.s,0,sizeof(T.s)); for (i=1;i<=2*m;i++) T.s[i][i]=1; while (l) { while (k>l) { k/=2; p--; } T=Matrix_Mul(T,_2M[p],m); l-=k; } return;}void _26P(int l){ node h; ans=0; h.s[1][1]=26; h.s[1][2]=1; h.s[2][1]=0; h.s[2][2]=1; getmatrix(h,2,l); ans=T.s[1][2]; }void getdata(){ _26P(l); getmatrix(h,m,l); for (int i=m+1;i<=2*m;i++) ans-=T.s[1][i]; return;}int main(){ while (~scanf("%d%d",&n,&l)) { Built_Trie(); Built_AC_Automation(); Built_Matrix(); getdata(); printf("%I64u\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。