[关闭]
@Jerusalem 2015-11-12T00:50:06.000000Z 字数 2691 阅读 1149

  POJ2778:


  很容易想到,本题是一道AC自动机上的DP。
  定义状态函数f(i,j),代表目标串的第i位匹配到了AC自动机中的节点j的方案数。
  那么显然,答案等于val[j]=0,last[j]=0f(n,j)
  考虑状态函数的转移,引入辅助函数P(i,j),代表从AC自动机的第i个节点转移到第j个节点的方案数,其中若i或j为危险节点,则P(i,j)=0
  容易发现,f(i,j)=f(i1,k)×P(k,j)
  这式子可以看作两个矩阵间的乘法,而P(i,j)可以简单地预处理出来。
  边界条件是,f(1,i)=1,其中i=ch[0][1]。

  

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <queue>
  8. typedef long long ll;
  9. using namespace std;
  10. const int maxnode=15*15,sigma=4;
  11. const int MOD=100000;
  12. queue<int> Q;
  13. struct Trie{
  14. int tot;
  15. int ch[maxnode][sigma];
  16. int f[maxnode];
  17. bool danger[maxnode];
  18. Trie(){
  19. tot=1;
  20. memset(ch,0,sizeof(ch));
  21. memset(f,0,sizeof(f));
  22. memset(danger,false,sizeof(danger));
  23. }
  24. inline int idx(char a){
  25. if(a=='A')
  26. return 0;
  27. if(a=='C')
  28. return 1;
  29. if(a=='G')
  30. return 2;
  31. return 3;
  32. }
  33. void Clear(){
  34. tot=1;
  35. memset(ch[0],0,sizeof(ch[0]));
  36. memset(danger,false,sizeof(danger));
  37. }
  38. int newnode(){
  39. memset(ch[tot],0,sizeof(ch[tot]));
  40. return tot++;
  41. }
  42. void Insert(string s){
  43. int len=s.length();
  44. int u=0;
  45. for(int i=0;i<len;i++){
  46. if(ch[u][idx(s[i])]==0)
  47. ch[u][idx(s[i])]=newnode();
  48. u=ch[u][idx(s[i])];
  49. }
  50. danger[u]=true;
  51. }
  52. void Build(){
  53. while(!Q.empty())
  54. Q.pop();
  55. for(int i=0;i<sigma;i++){
  56. if(ch[0][i]){
  57. f[ch[0][i]]=0;
  58. Q.push(ch[0][i]);
  59. }
  60. }
  61. while(!Q.empty()){
  62. int u=Q.front();
  63. Q.pop();
  64. for(int i=0;i<sigma;i++){
  65. if(ch[u][i]==0){
  66. ch[u][i]=ch[f[u]][i];
  67. continue;
  68. }
  69. int v=ch[u][i];
  70. Q.push(v);
  71. int r=f[u];
  72. while(r&&ch[r][i]==0)
  73. r=f[r];
  74. f[v]=ch[r][i];
  75. danger[v]|=danger[f[v]];
  76. }
  77. }
  78. }
  79. };
  80. struct Matrix{
  81. int l,r;
  82. ll a[maxnode][maxnode];
  83. Matrix(){
  84. l=r=0;
  85. memset(a,0,sizeof(a));
  86. }
  87. Matrix operator *(const Matrix& o)const{
  88. Matrix c;
  89. for(int i=0;i<=l;i++)
  90. for(int j=0;j<=o.r;j++)
  91. for(int k=0;k<=r;k++){
  92. c.a[i][j]+=(a[i][k]*o.a[k][j]);
  93. c.a[i][j]%=MOD;
  94. }
  95. c.l=l;
  96. c.r=o.r;
  97. return c;
  98. }
  99. void Print(){
  100. for(int i=0;i<=l;i++){
  101. for(int j=0;j<=r;j++)
  102. cout<<a[i][j]<<" ";
  103. printf("\n");
  104. }
  105. }
  106. };
  107. Trie Aho_Corasick;
  108. Matrix Base;
  109. Matrix E;
  110. Matrix From;
  111. int n;
  112. int m;
  113. string S;
  114. void First()
  115. {
  116. Aho_Corasick.Build();
  117. Base.l=Base.r=Aho_Corasick.tot-1;
  118. E.l=E.r=Base.l;
  119. From.l=0;
  120. From.r=Base.r;
  121. for(int i=0;i<=E.l;i++)
  122. E.a[i][i]=1;
  123. for(int i=0;i<=Base.l;i++)
  124. if(!Aho_Corasick.danger[i])
  125. for(int j=0;j<=Base.r;j++)
  126. if(!Aho_Corasick.danger[j])
  127. for(int k=0;k<sigma;k++)
  128. if(Aho_Corasick.ch[i][k]==j)
  129. Base.a[i][j]++;
  130. for(int j=0;j<sigma;j++)
  131. From.a[0][Aho_Corasick.ch[0][j]]++;
  132. }
  133. Matrix Power(Matrix O,int a)
  134. {
  135. Matrix ans=E;
  136. while(a>0){
  137. if(a&1)
  138. ans=ans*O;
  139. O=O*O;
  140. a>>=1;
  141. }
  142. return ans;
  143. }
  144. void Solve()
  145. {
  146. From=From*Power(Base,n-1);
  147. ll ans=0;
  148. for(int i=0;i<=From.r;i++)
  149. if(!Aho_Corasick.danger[i])
  150. ans+=From.a[0][i];
  151. cout<<ans%MOD;
  152. }
  153. void ReadData()
  154. {
  155. freopen("POJ2778.in","r",stdin);
  156. scanf("%d%d",&m,&n);
  157. for(int i=1;i<=m;i++){
  158. cin>>S;
  159. Aho_Corasick.Insert(S);
  160. }
  161. }
  162. void Close()
  163. {
  164. fclose(stdin);
  165. fclose(stdout);
  166. }
  167. int main()
  168. {
  169. ReadData();
  170. First();
  171. Solve();
  172. Close();
  173. return 0;
  174. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注