Descrtion
It’s well known that DNA Sequence is a sequence only contains A, C, T and G, and it’s very useful to analyze a segment of DNA Sequence，For example, if a animal’s DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the oblem is how many kinds of DNA sequences of a species don’t contain those segments.
Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.
男人的天堂 AV电影First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.
男人的天堂 AV电影Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.
Output
男人的天堂 AV电影An integer, the number of DNA sequences, mod 100000.
4 3
AT
AC
AG
AA
Sample Output
36
Solution
題目大意：給定m個字符串和一個長度n，求不包含這m個字符串的長度為n的字符串個數mod 100000的值，字符串中只含’A’、’C’、’T’、’G’。
做法：
首先構造一下AC自動機我們就會發現，題目要求的就是在AC自動機上跑n次同時不經過任何一個表示字符串的點的方案總數。仔細想一想會發現，有兩種點不合法：一是直接表示字符串的點，二是fail邊連向表示字符串的點的點。所以我們就可以DP，在構造AC自動機的時候給不合法的點打上標記。用fi,j表示跑了i次到達j節點的合法路徑總數，dp如下：
f[0][1]=1; //初始化
for(int i=1;i<=n;i++){ //n為輸入的字符串長度
for(int j=1;j<=num;j++){ //num為AC自動機中節點總數，1節點是根
if(!T[j].flag&&f[i-1][j]){
//如果該節點合法并且當前點的答案不為0（如果當前節點答案為0就沒必要更新了，更新等于沒更新）
for(int k=1;k<=4;k++){ //枚舉4種字母
int p=j;
while(!T[p].next[k])p=T[p].fail; //如果不匹配就沿著失配邊走（為了防止死循環，已經提早把T[0].next全部賦為1）
(f[i][T[p].next[k]]+=f[i-1][j])%=mod; //更新其他點的答案
}
}
}
}
但是這樣肯定不行，n有2?109，所以我們可以用矩陣乘法優化當前DP。矩陣還是容易推的，實在不懂看看代碼就行了。
代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=110,mod=100000;
struct node{
int next[5],fail,flag;
}T[maxn];
struct matrix{
LL a[maxn][maxn];
int l,r;
matrix(){memset(a,0,sizeof a);}
}temp,c,I;
int n,m,num=1,que[maxn],ans,head,tail,Hash[256];
char ch[12];
void Insert(char *s){
int p=1,len=strlen(s);
for(int i=0;i<len;i++){
if(!T[p].next[Hash[s[i]]])T[p].next[Hash[s[i]]]=++num;
p=T[p].next[Hash[s[i]]];
}
T[p].flag=true;
}
void Bfs(){ //構造AC自動機的fail邊，順便標記不合法節點
memset(que,head=tail=0,sizeof que);
que[++tail]=1;
while(head<tail){
int x=que[++head];
for(int i=1;i<=4;i++){
if(T[x].next[i]){
int p=T[x].fail;
while(!T[p].next[i])p=T[p].fail;
T[T[x].next[i]].fail=T[p].next[i];
if(T[T[p].next[i]].flag)T[T[x].next[i]].flag=true;
que[++tail]=T[x].next[i];
}
}
}
}
matrix mul(matrix x,matrix y){
matrix re;
re.l=x.l;re.r=y.r;
for(int i=1;i<=re.l;i++){
for(int j=1;j<=re.r;j++){
for(int k=1;k<=x.r;k++){
(re.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod;
}
}
}
return re;
}
matrix pow(matrix x,int y){
matrix re=I;
while(y){
if(y&1)re=mul(re,x);
x=mul(x,x);y>>=1;
}
return re;
}
int main(){
Hash['A']=1;Hash['C']=2;Hash['T']=3;Hash['G']=4;
for(int i=1;i<=4;i++)T[0].next[i]=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("\n%s",ch);
Insert(ch);
}
Bfs();temp.l=1;c.l=c.r=I.l=I.r=temp.r=num;
for(int i=1;i<=num;i++)I.a[i][i]=1;
for(int i=1;i<=num;i++){ //轉移矩陣
if(T[i].flag)continue;
for(int j=1;j<=4;j++){
int p=i;
while(!T[p].next[j])p=T[p].fail;
c.a[i][T[p].next[j]]++;
}
}
temp.a[1][1]=1;
temp=mul(temp,pow(c,m));
for(int i=1;i<=num;i++){ //統計答案
if(!T[i].flag){
(ans+=temp.a[1][i])%=mod;
}
}
printf("%d\n",ans);
return 0;
}
最新文章推薦