BZOJ 1009 [HNOI2008]GT考试 AC自动机+矩阵乘法

题意:链接略方法: AC自动机+矩阵乘法解析:和POJ 2778 一样的题。大概的思路就是我们建AC自动机的时候需要注意如果某个点是一个串的结尾的话，那么下面的节点都要看成结尾节点。然后按照AC自动机赋一下矩阵内部值就好了。赋的矩阵代表从一个节点走一步走到另一个节点有多少方案。然后经典模型，矩阵的n次方即可。代码:;int n,m,K;int size,root;int son[N][M];int fail[N];int end[N];char s[N];struct Matrix{int map[N][N];}a,ans;Matrix &mul(Matrix &a,Matrix &b){static Matrix ret;memset(ret.map,0,sizeof(ret.map));for(int i=1;i<=size;i++){for(int j=1;j<=size;j++){for(int k=1;k<=size;k++){ret.map[i][j]+=a.map[i][k]*b.map[k][j];}ret.map[i][j]%=K;}}return ret;}Matrix &Quick_Power(Matrix &a,int b){static Matrix ret;memset(ret.map,0,sizeof(ret.map));for(int i=1;i<=size;i++)ret.map[i][i]=1;while(b){if(b&1)ret=mul(ret,a);a=mul(a,a);b>>=1;}return ret;}void init(){memset(son,-1,sizeof(son));root=++size;}void ins(){int len=strlen(s+1);int now=root;for(int i=1;i<=len;i++){int alpha=s[i]-‘0’;if(son[now][alpha]==-1)son[now][alpha]=++size;now=son[now][alpha];}end[now]=1;}void build(){queue<int>q;for(int i=0;i<=9;i++){if(son[root][i]==-1)son[root][i]=root;else{fail[son[root][i]]=root;q.push(son[root][i]);}}while(!q.empty()){int u=q.front();q.pop();if(end[fail[u]])end[u]=1;for(int i=0;i<=9;i++){if(son[u][i]==-1)son[u][i]=son[fail[u]][i];else{fail[son[u][i]]=son[fail[u]][i];q.push(son[u][i]);}}}}void Build_Matrix(){for(int i=1;i<=size;i++){if(end[i])continue;for(int j=0;j<=9;j++){if(end[son[i][j]])continue;a.map[i][son[i][j]]++;}}}int main(){init();scanf(“%d%d%d”,&n,&m,&K);scanf(“%s”,s+1);ins();build();Build_Matrix();ans=Quick_Power(a,n);int print=0;for(int i=1;i<=size;i++)print=(print+ans.map[1][i])%K;printf(“%d\n”,print);}

，有多远，走多远，把足迹连成生命线。