题目地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2778
题目意思：给定你m个病毒串，和n,求长度为n的不包含任意一个病毒串的种数。n很大。
这个题和别的题不一样的地方就是n很大，那么我们首先得出n长度和n-1长度合法字符串之间的递推关系，是一个{zd0}为100*100的二维矩阵，然后我们采用快速矩阵乘法求解.
code：
#include<iostream>
#include<algorithm>
using namespace std;
const int kind = 4;
const int maxn = 102;
const int mod = 100000;
int inf,idx[100];
struct node {
int f,id;
node *fail;
node *next[kind+1];
};
struct matrix {
int g[maxn][maxn];
};
node list[maxn];
node *que[maxn],*root;
int nodeCnt;
inline node *newnode() {
node *ans = &list[++nodeCnt];
ans->fail = NULL;
ans->f = 0;
ans->id = nodeCnt;
for( int i = 0 ; i < kind; i++ )
ans->next[i] = NULL;
return ans;
}
void init() {
nodeCnt = 0;
root = newnode();
idx['A'] = 0;
idx['C'] = 1;
idx['G'] = 2;
idx['T'] = 3;
}
inline void insert(char *s) {
node *p = root;
while( *s ) {
int id = idx[*s];
if( p->next[id] == NULL ) p->next[id] = newnode();
p = p->next[id];
s++;
}
p->f = 1;
}
inline void ac_automation() {
int head = 0,i ,tail = 1;
que[head] = root;
node *p ,*tmp;
while( head < tail ) {
node *p = que[head++];
for( i = 0 ; i < kind ; i++)
if( p->next[i] != NULL ) {
if( p == root ) p->next[i]->fail = root;
else {
tmp = p->fail;
while( tmp!=NULL ) {
if( tmp->next[i] != NULL) {
p->next[i]->fail = tmp->next[i];
if( tmp->next[i]->f == 1) p->next[i]->f = 1;
break;
}
tmp=tmp->fail;
}
if( tmp == NULL ) p->next[i]->fail = root;
}
que[tail++] = p->next[i];
}
}
}
int n;
char s[105];
inline matrix multi( matrix x,matrix y) {
int i, j , k;
matrix ans;
memset(ans.g,0,sizeof(ans.g));
for( k = 1 ; k <= nodeCnt; k++ )
for( i = 1 ; i<=nodeCnt; i++ )
if( x.g[i][k] )
for( j = 1 ; j <= nodeCnt; j++ )
ans.g[i][j] = (ans.g[i][j]+ (1ll*x.g[i][k]*y.g[k][j])%mod)%mod;
return ans;
}
void solve() {
matrix st , tmp ;
int i,j;
memset(st.g,0,sizeof(st.g));
tmp = st;
for( i = 1 ; i <= nodeCnt; i++ )
if( list[i].f == 0 )
for( j = 0 ; j < kind; j++ ) {
node *p = &list[i];
if( p->next[j] == NULL ) {
p = p->fail;
while( p ) {
if( p->next[j] != NULL ) break;
p = p->fail;
}
if( p == NULL ) p = root;
else p = p->next[j];
}
else p = p->next[j];
if( p->f == 0) st.g[i][p->id]++;
}
tmp.g[1][1] = 1;
while( n ) {
if( n&1 ) tmp = multi(tmp,st);
st = multi(st,st);
n >>= 1;
}
int ans = 0;
for( i = 1 ; i <= nodeCnt; i++ ) {
ans = (ans + tmp.g[1][i])%mod;
}
cout<<ans<<endl;
}
int main() {
int m,i,j;
while( scanf("%d%d",&m,&n) != EOF) {
init();
for( i = 0 ; i < m; i++ ) {
scanf("%s",s);
insert(s);
}
ac_automation();
solve();
}
}
