DNA Sequence
题意：题目给m个病毒串，问不包含病毒串的长度为n的DNA p段有几个
难度：两颗星
思路：
这个图是例子{“ACG”,”C”},构建树后如图所示，从每个结点出发都有4条边（A,T,C,G）
•从状态0出发走一步有4种走法：
–走A到状态1（安全）；
–走C到状态4（危险）；
–走T到状态0（安全）；
–走G到状态0（安全）；
•所以当n=1时，答案就是3
•当n=2时，就是从状态0出发走2步，就形成一个长度为2的字符串，只要路径上没有经过危险结点，有几种走法，那么答案就是几种。依此类推走n步就形成长度为n的字符串。
matrix矩阵如下(矩阵i行j列的权值是结点i转移到结点j的方案数)：
n=1
2 1 0 0 0
2 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
n=2
6 3 0 0 0
6 3 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
代码+注释：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
int ch[111][4],f[111],sz;
int idx[128]; //病毒只有4个字符，可以简单处理
bool val[111];
/*题目的数据范围是10个长度10的病毒串，所以Trie树中最多101左右个节点，
那么AC自动机整个转移就可以构建一张101*101的邻接矩阵，矩阵i行j列的权值是节点i转移到节点j的方案数。
而进行k次转移，从节点i转移到节点j的方案数是这个矩阵的k次幂，这个结论离散数学的图论有（我没学，只能信了）*/
struct Trie{
Trie(){ sz = 0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);};
void insert(char *s){
int u=0;
for(int i=0;s[i];++i){
int c=idx[s[i]];
if(!ch[u][c]) ch[u][c] = ++sz;
u=ch[u][c];
}
val[u]=1; //val数组标记节点是否为单词结尾，last数组和val数组是同一个数组，没必要都要，所以这里没有last数组
}
};
//fail指针没必要初始化，从前往后计算会覆盖上一次的结果
int getFail(){
queue<int>q; int u;
f[0] = 0;
for(int c=0;c<4;++c){
u = ch[0][c];
if(u) { f[u]=0; q.push(u);}
}
while(!q.empty()){
int r=q.front(); q.pop();
for(int c=0;c<4;++c){
u=ch[r][c];
if(!u){
ch[r][c]=ch[f[r]][c]; //移花接木，因为是从前往后计算的，如果当前位置没有节点，
//而前面有这条边，则将最近的一个边的出节点复制过来，方便后续寻找fail指针的简化，只要找一次就能得到fail指针
//因为是将前面的节点移过来，所以不必再对这个节点继续操作了
continue;
}
q.push(u);
f[u] = ch[f[r]][c]; //可以直接这样得益于上面移花接木的操作
val[u]|=val[ch[f[r]][c]]; //如果该节点的fail指针是单词结尾，这个节点也不能取
/*只要算出后缀含有病毒的点即可，因为矩阵是通过相互到达传递的，
其后的点只有这个危险点能到达，危险点的行和列全是0，则其后的点也不会参与运算。
可以这样说，0行里危险点的列和其后的列从来都是0，因为不能到达。*/
}
}
}
struct mat {
ll matrix[111][111];
mat() {
memset(matrix,0,sizeof(matrix));
}
};
mat operator*(const mat &m1,const mat &m2){
mat m;
for(int i=0; i<=sz; ++i){
for(int j=0; j<=sz; ++j){
for(int k=0; k<=sz; ++k){
m.matrix[i][j]+=m1.matrix[i][k]*m2.matrix[k][j];
m.matrix[i][j]%=100000;
}
}
}
return m;
}
char str[11];
int m,n;
int main(){
idx['A']=0; idx['C']=1; idx['T']=2; idx['G']=3;
while(~scanf("%d%d",&m,&n)) {
Trie trie;
while(m--){
scanf("%s",str);
trie.insert(str);
}
getFail();
mat res,a;
for(int i=0;i<=sz;++i) res.matrix[i][i]=1;
for(int i=0;i<=sz;++i) {
if(val[i]) continue;
for(int j=0;j<4;++j) {
if(val[ch[i][j]]) continue;
++a.matrix[i][ch[i][j]];
}
}
for(int i=0;i<=sz;++i) {//打印矩阵
for(int j=0;j<=sz;++j) {
printf("%d ",a.matrix[i][j]);
}
puts("");
}
while(n) {
if(n&1) res=res*a;
a=a*a;
n>>=1;
}
for(int i=0;i<=sz;++i) {//打印矩阵
for(int j=0;j<=sz;++j) {
printf("%d ",res.matrix[i][j]);
}
puts("");
}
ll ans=0;
for(int i=0;i<=sz;++i)
ans=(ans+res.matrix[0][i])%100000;
//所有串都是从根节点开始的
printf("%lld\n",ans);
}
}无注释代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
int ch[111][4],f[111],sz;
int idx[128];
bool val[111];
struct Trie{
Trie(){ sz = 0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);};
void insert(char *s){
int u=0;
for(int i=0;s[i];++i){
int c=idx[s[i]];
if(!ch[u][c]) ch[u][c] = ++sz;
u=ch[u][c];
}
val[u]=1;
}
};
int getFail(){
queue<int>q; int u;
f[0] = 0;
for(int c=0;c<4;++c){
u = ch[0][c];
if(u) { f[u]=0; q.push(u);}
}
while(!q.empty()){
int r=q.front(); q.pop();
for(int c=0;c<4;++c){
u=ch[r][c];
if(!u){
ch[r][c]=ch[f[r]][c];
continue;
}
q.push(u);
f[u] = ch[f[r]][c];
val[u]|=val[ch[f[r]][c]];
}
}
}
struct mat {
ll matrix[111][111];
mat() {
memset(matrix,0,sizeof(matrix));
}
};
mat operator*(const mat &m1,const mat &m2){
mat m;
for(int i=0; i<=sz; ++i){
for(int j=0; j<=sz; ++j){
for(int k=0; k<=sz; ++k){
m.matrix[i][j]+=m1.matrix[i][k]*m2.matrix[k][j];
m.matrix[i][j]%=100000;
}
}
}
return m;
}
char str[11];
int m,n;
int main(){
idx['A']=0; idx['C']=1; idx['T']=2; idx['G']=3;
while(~scanf("%d%d",&m,&n)) {
Trie trie;
while(m--){
scanf("%s",str);
trie.insert(str);
}
getFail();
mat res,a;
for(int i=0;i<=sz;++i) res.matrix[i][i]=1;
for(int i=0;i<=sz;++i) {
if(val[i]) continue;
for(int j=0;j<4;++j) {
if(val[ch[i][j]]) continue;
++a.matrix[i][ch[i][j]];
}
}
while(n) {
if(n&1) res=res*a;
a=a*a;
n>>=1;
}
ll ans=0;
for(int i=0;i<=sz;++i)
ans=(ans+res.matrix[0][i])%100000;
printf("%lld\n",ans);
}
}