首页 > 代码库 > 【POJ2778】DNA Sequence(AC自动机)
【POJ2778】DNA Sequence(AC自动机)
题意:
生物课上我们学到,DNA序列中只有A, C, T和G四种片段。
经科学发现,DNA序列中,包含某些片段会产生不好的基因,如片段”ATC”是不好片段,则”AGATCC”, “CATCAA”, “ATCATC”都是不好的DNA序列,这些不好片段我们可以称为病毒片段。
现在已知m个病毒片段, 问长度为n的DNA序列,有多少种可能不包含病毒片段。答案可能很大,取模 100000。
【数据规模和约定】
0<=m<=10 病毒片段长度不超过10,只含A,T,C,G字母
1<=n<=2000000000
思路:AC自动机
因为fail[i]一定是i的一个前缀的后缀,fail[i]如果带病毒i必定带病毒
转移:
{
dp[0,1]:=1;
for i:=1 to m do
for eachedge(i,j)
begin
dp[i,j]:=dp[i,j]+dp[i-1,i];
end; }
用矩阵乘法优化
1 const mo=100000; 2 type arr=array[1..110,1..110]of int64; 3 var y,c,ans,d:arr; 4 s:array[1..4]of char; 5 map:array[1..10000,‘A‘..‘Z‘]of longint; 6 f,b,q:array[1..200000]of longint; 7 m,n,i,j,k,t,sum,num:longint; 8 ch:string; 9 10 procedure build; 11 var i,k,d:longint; 12 begin 13 k:=1; d:=length(ch); 14 for i:=1 to d do 15 begin 16 if map[k,ch[i]]=0 then begin inc(num); map[k,ch[i]]:=num; end; 17 k:=map[k,ch[i]]; 18 end; 19 b[k]:=1; 20 end; 21 22 procedure acauto; 23 var t,w,i,u,p,son:longint; 24 begin 25 t:=0; w:=1; q[1]:=1; 26 while t<w do 27 begin 28 inc(t); u:=q[t]; 29 for i:=1 to 4 do 30 if map[u,s[i]]>0 then 31 begin 32 son:=map[u,s[i]]; 33 p:=f[u]; 34 if u=1 then f[son]:=1 35 else f[son]:=map[p,s[i]]; 36 inc(w); q[w]:=son; 37 end 38 else 39 begin 40 p:=f[u]; 41 if u=1 then map[u,s[i]]:=1 42 else map[u,s[i]]:=map[p,s[i]]; 43 end; 44 end; 45 end; 46 47 begin 48 assign(input,‘poj2778.in‘); reset(input); 49 assign(output,‘poj2778.out‘); rewrite(output); 50 readln(m,n); 51 num:=1; 52 s[1]:=‘A‘; s[2]:=‘C‘; s[3]:=‘G‘; s[4]:=‘T‘; 53 for i:=1 to m do 54 begin 55 readln(ch); 56 build; 57 end; 58 acauto; 59 for i:=2 to num do 60 if b[f[i]]=1 then b[i]:=1; 61 62 for i:=1 to num do 63 if b[i]=0 then 64 for j:=1 to 4 do 65 if b[map[i,s[j]]]=0 then inc(d[i,map[i,s[j]]]); 66 67 t:=n; 68 for i:=1 to num do ans[i,i]:=1; 69 y:=d; 70 while t>0 do 71 begin 72 if t and 1=1 then 73 begin 74 for i:=1 to num do 75 for j:=1 to num do c[i,j]:=0; 76 for i:=1 to num do 77 for k:=1 to num do 78 begin 79 for j:=1 to num do c[i,k]:=c[i,k]+ans[i,j]*y[j,k]; 80 c[i,k]:=c[i,k] mod mo; 81 end; 82 for i:=1 to num do 83 for j:=1 to num do ans[i,j]:=c[i,j]; 84 end; 85 for i:=1 to num do 86 for j:=1 to num do c[i,j]:=0; 87 for i:=1 to num do 88 for k:=1 to num do 89 begin 90 for j:=1 to num do c[i,k]:=c[i,k]+y[i,j]*y[j,k]; 91 c[i,k]:=c[i,k] mod mo; 92 end; 93 for i:=1 to num do 94 for j:=1 to num do y[i,j]:=c[i,j]; 95 t:=t>>1; 96 end; 97 for i:=1 to num do sum:=(sum+ans[1,i]) mod mo; 98 writeln(sum); 99 100 101 close(input); 102 close(output); 103 end.
【POJ2778】DNA Sequence(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。