DNA Sequence
题意
在由‘A’, ‘C’ ,‘T’ ,‘G’ 组成的DNA序列中有一些基因片段携带遗传病 。如果某个DNA序列中包含一个或多个这样的基因片段 ，那么这个DNA序列是有遗传病的 。
现在给 m 个基因片段 s
i
。问所有长度为 n 的DNA序列中 ，有多少个没有遗传病 ，答案模100000 。
（其中 0<= m,s
i
,<= 10 , 1 <= n <= 2000000000）
input
4 3
AT
AC
AG
AA
output
36
思路
这题一个很巧妙的地方是用到了矩阵快速幂来处理这个非常大的n。
离散数学学过一个东西 —— 对一个图的邻接矩阵求n次幂后 ， a
i
j
的值代表从 i 号节点通过n步走到 j 号节点所用的方案数 。，这正是我们所需要的。
将m个字串构建成带fail指针的 Trie 树 ，将字符串的结束位置打上标记 （和普通的AC自动机一样）。
那么没有遗传病的长度为n的DNA序列 ， 就是我们从根节点开始走n步且不经过标记点的所有走法。
于是，对于建好的trie树，如果当前节点和后续节点都没有被标记，那就将它们连一条边，存在邻接矩阵里。将邻接矩阵取n次幂，将所有的 a[root][i] 加起来即可。
这题要注意一点，做矩阵乘法时不要次次取模 ， 而是处理完一行再取模，否则会TLE。
代码
#include<iostream>
#include <map>
#include <queue>
#include <cstring>
using namespace std;
long long n,m;
const int mod = 100000;
string ss[15];
map<char,int> func;
struct trie{
int nxt[2050][4]; // kuangbin的板子
int fail[2050];
bool end[2050];
int idx,root;
int newnode(){
for(int i=0;i<4;i++)
nxt[idx][i] = -1;
end[idx] = false;
idx++;
return idx-1;
}
void init(){
idx = 0;
root = newnode();
}
void insert(string buf){
int len = buf.length();
int now = root;
for(int i=0;i<len;i++){
if(nxt[now][func[buf[i]]]==-1)
nxt[now][func[buf[i]]] = newnode();
now = nxt[now][func[buf[i]]];
}
end[now] = true; // 字符串结束的位置打上标记
}
void build(){
queue<int> q;
fail[root] = root;
for(int i=0;i<4;i++){
if(nxt[root][i]==-1)
nxt[root][i] = root;
else{
fail[nxt[root][i]] = root;
q.push(nxt[root][i]);
}
}
while(!q.empty()){
int now = q.front();
q.pop();
for(int i=0;i<4;i++){
if(nxt[now][i]==-1)
nxt[now][i] = nxt[fail[now]][i];
else{
fail[nxt[now][i]] = nxt[fail[now]][i];
q.push(nxt[now][i]);
}
//注意AC自动机中末尾节点会连回失配指针的位置，即 nxt[now][i] = nxt[fail[now]][i]
// 所以此时得对nxt[now][i] 是否应该被标记再做一次判断
end[nxt[now][i]] |= end[nxt[fail[now]][i]];
}
}
}
};
trie tr;
// 矩阵快速幂
struct matrix{
long long a[105][105];
matrix() {
memset(a, 0, sizeof(a));
}
void print(){
cout<<"now"<<endl;
for(int i=0;i<=tr.idx;i++){
for(int j=0;j<=tr.idx;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
};
matrix operator*(const matrix &x,const matrix &y){
matrix mx;
for (int i = 0; i <= tr.idx; i++){
for (int j = 0; j <= tr.idx; j++){
for (int k = 0; k <= tr.idx; k++){
mx.a[i][j] = (mx.a[i][j] + x.a[i][k] * y.a[k][j]);
}
mx.a[i][j] %=mod; //处理完一行再取模
}
}
return mx;
}
matrix ksm(matrix ax,long long b){
matrix res;
for(int i=0;i<=tr.idx;i++) res.a[i][i] = 1;
while(b){
if (b & 1) res = res * ax;
ax = ax * ax;
b >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
tr.init();
func['A'] = 0,func['C'] = 1,func['T'] = 2,func['G'] = 3;
for(int i=1;i<=n;i++){
cin>>ss[i];
tr.insert(ss[i]);
}
tr.build();
matrix ans;
for(int i=0;i<=tr.idx;i++){
for(int j=0;j<4;j++){
if(tr.end[i]==0&&tr.end[tr.nxt[i][j]]==0){
ans.a[i][tr.nxt[i][j]]++; //邻接矩阵连边
}
}
}
ans = ksm(ans,m);
int sum = 0;
for(int i=0;i<=tr.idx;i++){
sum = (int)(sum+ans.a[0][i]%mod)%mod;
}
cout<<sum%mod<<endl;
return 0;
}