1 条题解
-
0
DNA序列安全计数 - 解题思路
这段代码使用AC自动机和矩阵快速幂来计算长度为n且不包含任何禁止DNA子串的安全DNA序列数量。
算法思路
-
AC自动机构建:
- 初始化字符映射(A→0, C→1, T→2, G→3)
- 插入所有禁止DNA子串到Trie树中
- 构建失败指针(类似KMP的next数组),形成AC自动机
- 标记所有终止节点(包含禁止子串的节点)
-
状态转移矩阵构建:
- 创建状态转移矩阵,矩阵大小由Trie节点数决定
- 遍历所有非终止节点,统计合法转移(不导致禁止子串的转移)
-
矩阵快速幂计算:
- 使用快速幂算法计算转移矩阵的n次幂
- 累加从初始状态(0)到所有非终止状态的路径数
-
结果输出:
- 输出长度为n的安全DNA序列总数,结果对100000取模
关键点
- 使用AC自动机高效处理多模式串匹配
- 利用矩阵表示状态转移关系
- 通过矩阵快速幂在O(log n)时间内计算高次幂
- 动态规划思想统计所有可能路径
- 模运算防止数值溢出
该算法能高效计算不包含任何禁止子串的DNA序列数量,适用于较大的n值。
#include<cstdio> #include<cstring> #include<queue> using namespace std; int ch[111][4],fail[111],tn; bool flag[111]; int idx[128]; void insert(char *s){ int x=0; for(int i=0; s[i]; ++i){ int y=idx[s[i]]; if(ch[x][y]==0) ch[x][y]=++tn; x=ch[x][y]; } flag[x]=1; } void init(){ memset(fail,0,sizeof(fail)); queue<int> que; for(int i=0; i<4; ++i){ if(ch[0][i]) que.push(ch[0][i]); } while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0; i<4; ++i){ if(ch[now][i]) que.push(ch[now][i]),fail[ch[now][i]]=ch[fail[now]][i]; else ch[now][i]=ch[fail[now]][i]; flag[ch[now][i]]|=flag[ch[fail[now]][i]]; } } } struct Mat{ long long mat[111][111]; Mat(){ memset(mat,0,sizeof(mat)); } }; Mat operator*(const Mat &m1,const Mat &m2){ Mat m; for(int i=0; i<=tn; ++i){ for(int j=0; j<=tn; ++j){ for(int k=0; k<=tn; ++k){ m.mat[i][j]+=m1.mat[i][k]*m2.mat[k][j]; m.mat[i][j]%=100000; } } } return m; } int main(){ idx['A']=0; idx['C']=1; idx['T']=2; idx['G']=3; char str[11]; int m,n; while(~scanf("%d%d",&m,&n)){ tn=0; memset(flag,0,sizeof(flag)); memset(ch,0,sizeof(ch)); while(m--){ scanf("%s",str); insert(str); } init(); Mat e,x; for(int i=0; i<=tn; ++i) e.mat[i][i]=1; for(int i=0; i<=tn; ++i){ if(flag[i]) continue; for(int j=0; j<4; ++j){ if(flag[ch[i][j]]) continue; ++x.mat[i][ch[i][j]]; } } while(n){ if(n&1) e=e*x; x=x*x; n>>=1; } long long res=0; for(int i=0; i<=tn; ++i){ res+=e.mat[0][i]; res%=100000; } printf("%lld\n",res); } return 0; }
-
- 1
信息
- ID
- 1778
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者