BJOI2011 day3 禁忌 taboo

描述

随机吐出一个长为lenth的字符串，求E("最多包含多少个禁忌词")。E表示数学期望。

思路

AC自动机+DP+矩阵乘法。。。

代码

#include
#include
#include
#include
using namespace std;
#define NMAX 101
int alpha,num;
struct node
{int name;bool end;node *next[26],*fa,*fail;node(){end=0;fail=NULL;memset(next,0,sizeof(next));}
}epool[NMAX],*etop,*head;
void init()
{etop=epool;head=etop++;
}
void add(char *c)
{node *p=head;for (int i=0;inext[x]){etop->fa=p;etop->name=x;p->next[x]=etop++;}p=p->next[x];}p->end=1;
}
node *Q[NMAX];
void build_ac()
{int top,bot;top=bot=0;Q[bot++]=head;node *t,*p;while(topfa==head) t->fail=head;else if (t!=head){int x=t->name;p=t->fa->fail;t->fail=p->next[x];t->end|=p->next[x]->end;}for (int i=0;inext[i]) Q[bot++]=t->next[i];else{if (t==head) t->next[i]=head;else t->next[i]=t->fail->next[i];}}}
}
struct matrix
{long double a[NMAX][NMAX];matrix(){memset(a,0,sizeof(a));}
};
matrix operator * (const matrix &x,const matrix &y)
{matrix ret;for (int i=0;i>=1;}return ret.a[0][num-1];
}
matrix G;
void buildG()
{node *t;num=etop-epool+1;for (int i=0;inext[j]-epool;if (t->next[j]->end){G.a[i][0]+=1./alpha;G.a[i][num-1]+=1./alpha;}elseG.a[i][jaddr]+=1./alpha;}}G.a[num-1][num-1]=1;
}
void prG()
{printf("NUM=%d\n",num);for (int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！