poj2778DNASequence(AC自动机+矩阵快速幂）

DNA Sequence

题意

在由‘A’, ‘C’ ,‘T’ ,‘G’ 组成的DNA序列中有一些基因片段携带遗传病 。如果某个DNA序列中包含一个或多个这样的基因片段 &＃xff0c;那么这个DNA序列是有遗传病的 。

现在给 m 个基因片段 s_i 。问所有长度为 n 的DNA序列中 &＃xff0c;有多少个没有遗传病 &＃xff0c;答案模100000 。

&＃xff08;其中 0<&＃61; m,s_i ,<&＃61; 10 , 1 <&＃61; n <&＃61; 2000000000&＃xff09;

input

4 3
AT
AC
AG
AA

output

36

思路

这题一个很巧妙的地方是用到了矩阵快速幂来处理这个非常大的n。
离散数学学过一个东西 ------ 对一个图的邻接矩阵求n次幂后 &＃xff0c; a_ij 的值代表从 i 号节点通过n步走到 j 号节点所用的方案数 。&＃xff0c;这正是我们所需要的。
将m个字串构建成带fail指针的 Trie 树 &＃xff0c;将字符串的结束位置打上标记 &＃xff08;和普通的AC自动机一样&＃xff09;。那么没有遗传病的长度为n的DNA序列 &＃xff0c; 就是我们从根节点开始走n步且不经过标记点的所有走法。 于是&＃xff0c;对于建好的trie树&＃xff0c;如果当前节点和后续节点都没有被标记&＃xff0c;那就将它们连一条边&＃xff0c;存在邻接矩阵里。将邻接矩阵取n次幂&＃xff0c;将所有的 a[root][i] 加起来即可。
这题要注意一点&＃xff0c;做矩阵乘法时不要次次取模 &＃xff0c; 而是处理完一行再取模&＃xff0c;否则会TLE。

样例的图大概长这样&＃xff08;灵魂画法.jpg) &＃xff1a;

代码

#include
#include
#include
#include
using namespace std;
long long n,m;
const int mod &＃61; 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&＃61;0;i<4;i&＃43;&＃43;)nxt[idx][i] &＃61; -1;end[idx] &＃61; false;idx&＃43;&＃43;;return idx-1;}void init(){idx &＃61; 0;root &＃61; newnode();}void insert(string buf){int len &＃61; buf.length();int now &＃61; root;for(int i&＃61;0;i<len;i&＃43;&＃43;){if(nxt[now][func[buf[i]]]&＃61;&＃61;-1)nxt[now][func[buf[i]]] &＃61; newnode();now &＃61; nxt[now][func[buf[i]]];}end[now] &＃61; true; // 字符串结束的位置打上标记}void build(){queue<int> q;fail[root] &＃61; root;for(int i&＃61;0;i<4;i&＃43;&＃43;){if(nxt[root][i]&＃61;&＃61;-1)nxt[root][i] &＃61; root;else{fail[nxt[root][i]] &＃61; root;q.push(nxt[root][i]);}}while(!q.empty()){int now &＃61; q.front();q.pop();for(int i&＃61;0;i<4;i&＃43;&＃43;){if(nxt[now][i]&＃61;&＃61;-1)nxt[now][i] &＃61; nxt[fail[now]][i];else{fail[nxt[now][i]] &＃61; nxt[fail[now]][i];q.push(nxt[now][i]);}//注意AC自动机中末尾节点会连回失配指针的位置&＃xff0c;即 nxt[now][i] &＃61; nxt[fail[now]][i]// 所以此时得对nxt[now][i] 是否应该被标记再做一次判断end[nxt[now][i]] |&＃61; 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&＃61;0;i<&＃61;tr.idx;i&＃43;&＃43;){for(int j&＃61;0;j<&＃61;tr.idx;j&＃43;&＃43;){cout<<a[i][j]<<" ";}cout<<endl;}}
};
matrix operator*(const matrix &x,const matrix &y){matrix mx;for (int i &＃61; 0; i <&＃61; tr.idx; i&＃43;&＃43;){for (int j &＃61; 0; j <&＃61; tr.idx; j&＃43;&＃43;){for (int k &＃61; 0; k <&＃61; tr.idx; k&＃43;&＃43;){mx.a[i][j] &＃61; (mx.a[i][j] &＃43; x.a[i][k] * y.a[k][j]);}mx.a[i][j] %&＃61;mod; //处理完一行再取模}}return mx;
}
matrix ksm(matrix ax,long long b){matrix res;for(int i&＃61;0;i<&＃61;tr.idx;i&＃43;&＃43;) res.a[i][i] &＃61; 1;while(b){if (b & 1) res &＃61; res * ax;ax &＃61; ax * ax;b >>&＃61; 1;}return res;
}int main(){ios::sync_with_stdio(false);cin>>n>>m;tr.init();func[&＃39;A&＃39;] &＃61; 0,func[&＃39;C&＃39;] &＃61; 1,func[&＃39;T&＃39;] &＃61; 2,func[&＃39;G&＃39;] &＃61; 3;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cin>>ss[i];tr.insert(ss[i]);}tr.build();matrix ans;for(int i&＃61;0;i<&＃61;tr.idx;i&＃43;&＃43;){for(int j&＃61;0;j<4;j&＃43;&＃43;){if(tr.end[i]&＃61;&＃61;0&&tr.end[tr.nxt[i][j]]&＃61;&＃61;0){ans.a[i][tr.nxt[i][j]]&＃43;&＃43;; //邻接矩阵连边}}}ans &＃61; ksm(ans,m);int sum &＃61; 0;for(int i&＃61;0;i<&＃61;tr.idx;i&＃43;&＃43;){sum &＃61; (int)(sum&＃43;ans.a[0][i]%mod)%mod;}cout<<sum%mod<<endl;return 0;
}