这题的意思是,给你n个长度不超过5的字符串,求有多少个长度为至少为L的字符串,里面至少包含n个字符串中的一个。
这题和求DNA片段的差不多啦,只不过L的条件有点变化。
假设矩阵A里储存着字符间的可行转移,那么A^L就代表了长度为L的不包含n个字符串中任何一个的个数。
最终的答案就是26^1+26^2+......+26^L减去A^1+A^2+....+A^L
矩阵A可以用ac自动机维护一个跳转表得到。接下来就是考虑如何快速的求得A^1+A^2+....+A^L了。
根据矩阵的性质
|A , 1| |A^n , 1+A^1+A^2+....+A^(n-1)|
|0 , 1| 的n次方等于|0 , 1|
所以我们只需要将A矩阵扩大四倍,变成如上形式的矩阵B,然后开L+1次方就可以得到1+A^1+A^2+....+A^L。由于多了一个1,所以最后得到的答案我们还要减去一个单位矩阵。
另外,我们也可以根据二分的性质来求解,当n==6时,有
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
最后我们将B矩阵右上部分的第一列加起来,便是答案了。另外一点,2^64次方,需要用unsigned __int64储存
View Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 using namespace std; 5 #define LL unsigned __int64 6 7 struct node 8 { 9 int cnt; 10 struct node *fail; 11 struct node *next[26]; 12 struct node *jump[26]; 13 }; 14 15 node root[33]; 16 int num; 17 char str[10]; 18 LL mod=10330176681277348905; 19 20 void insert(char word[]) 21 { 22 int i=0; 23 node *tmp=root; 24 while(word[i]) 25 { 26 int b=word[i]-'a'; 27 if(tmp->next[b]==NULL) 28 { 29 tmp->next[b]=root+num; 30 memset(root+num,0,sizeof(struct node)); 31 num++; 32 } 33 tmp=tmp->next[b]; 34 i++; 35 } 36 tmp->cnt=1; 37 } 38 39 node *q[33]; 40 int head,tail; 41 42 void add_fail() 43 { 44 head=tail=0; 45 q[tail++]=root; 46 while(head<tail) 47 { 48 node *x=q[head++]; 49 for(int i=0;i<26;i++) 50 { 51 node *t=x->fail; 52 while(t!=NULL && t->next[i]==NULL) 53 t=t->fail; 54 if(x->next[i]!=NULL) 55 { 56 q[tail++]=x->next[i]; 57 if(t==NULL) 58 x->next[i]->fail=root; 59 else 60 { 61 x->next[i]->fail=t->next[i]; 62 if(t->next[i]->cnt) 63 x->next[i]->cnt=1; 64 } 65 x->jump[i]=x->next[i]; 66 } 67 else 68 { 69 if(t==NULL) 70 x->jump[i]=root; 71 else 72 x->jump[i]=t->next[i]; 73 } 74 } 75 } 76 } 77 78 int m; 79 int n; 80 81 struct Mat 82 { 83 LL a[2*33][2*33]; 84 void init() 85 { 86 int i,j; 87 for(i=0;i<2*33;i++) 88 for(j=0;j<2*33;j++) 89 a[i][j]=0; 90 } 91 }; 92 int len; 93 Mat e; 94 95 Mat mul(Mat a,Mat b) 96 { 97 Mat res; 98 int i,j,k; 99 for(i=0;i<2*len;i++) 100 { 101 for(j=0;j<2*len;j++) 102 { 103 res.a[i][j]=0; 104 for(k=0;k<2*len;k++) 105 { 106 if(a.a[i][k]>0 && b.a[k][j]>0) 107 { 108 res.a[i][j]+=a.a[i][k]*b.a[k][j]; 109 } 110 } 111 } 112 } 113 return res; 114 } 115 116 117 LL solve(Mat a,int k) 118 { 119 Mat b,ans=e; 120 int i,j; 121 b.init(); 122 for(i=0;i<len;i++) //左上部分 123 for(j=0;j<len;j++) 124 b.a[i][j]=a.a[i][j]; 125 for(i=0;i<len;i++) //右上部分 126 { 127 for(j=len;j<2*len;j++) 128 b.a[i][j]=(i==j-len); 129 } 130 for(i=len;i<2*len;i++) //右下部分 131 { 132 for(j=len;j<2*len;j++) 133 b.a[i][j]=(i==j); 134 } 135 k++; 136 while(k) 137 { 138 if(k&1) 139 { 140 ans=mul(ans,b); 141 } 142 b=mul(b,b); 143 k/=2; 144 } 145 LL res=0; 146 for(i=0;i<len;i++) 147 { 148 res+=ans.a[i][len]; 149 } 150 return res-1; 151 } 152 153 LL sum(LL a,int k) 154 { 155 Mat b; 156 Mat ans=e; 157 b.init(); 158 b.a[0][0]=26;b.a[0][1]=1; 159 b.a[1][0]=0; b.a[1][1]=1; 160 k++; 161 while(k) 162 { 163 if(k&1) 164 { 165 ans=mul(ans,b); 166 } 167 b=mul(b,b); 168 k/=2; 169 } 170 return ans.a[0][1]-1; 171 } 172 173 int main() 174 { 175 int i,j,k; 176 for(i=0;i<2*33;i++) 177 for(j=0;j<2*33;j++) 178 e.a[i][j]=(i==j); 179 freopen("D:\\in.txt","r",stdin); 180 while(scanf("%d%d",&n,&m)==2) 181 { 182 num=1; 183 memset(root,0,sizeof(struct node)); 184 for(i=0;i<n;i++) 185 { 186 scanf("%*c%s",str); 187 insert(str); 188 } 189 add_fail(); 190 int id=0,id1; 191 Mat res; 192 for(i=0;i<num;i++) 193 { 194 if(root[i].cnt==0) 195 { 196 id1=0; 197 for(j=0;j<num;j++) 198 { 199 if(root[j].cnt==0) 200 { 201 LL count=0; 202 for(k=0;k<26;k++) 203 { 204 if(root[j].jump[k]==root+i) 205 { 206 count++; 207 } 208 } 209 res.a[id][id1]=count; 210 id1++; 211 } 212 } 213 id++; 214 } 215 } 216 len=id; 217 LL all=sum(26,m); //26+26^1+26^2+....+26^m 218 LL left=solve(res,m); //A+A^1+A^2+....+A^m 219 all-=left; 220 if(all<0) 221 all+=mod; 222 printf("%I64u\n",all); 223 } 224 return 0; 225 }