首页 > 代码库 > 【AC自动机】【高斯消元】hdu5955 Guessing the Dice Roll
【AC自动机】【高斯消元】hdu5955 Guessing the Dice Roll
http://blog.csdn.net/viphong/article/details/53098489
我有一点不是很懂,这样算出来转移到AC自动机根节点的概率是一个远大于1的数。
按我的理解,因为转移初始就是从根节点出发的,
所以x(0)存储的是从根节点出发的概率(100%)+其他点转移到根节点的概率……
比较抽象,还是当做套路记住吧……(鶸的做法)
#include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std; #define N 110 double B[N][N+1],A[N][N+1],x[N],b[N]; int ma[13],size; void guass_jordan() { int n=size; memcpy(B,A,sizeof(A)); for(int i=1;i<=n;++i) B[i][n+1]=b[i]; for(int i=1;i<=n;++i)//枚举:正在消除第i个未知数,之后第i个方程废掉,矩阵行、列-1 { int pivot=i; for(int j=i+1;j<=n;++j)//枚举j:把正在处理的未知数的系数的绝对值最大的方程换到第i行 if(fabs(B[j][i])>fabs(B[pivot][i])) pivot=j; swap(B[i],B[pivot]); //if(fabs(B[i][i])<EPS) //若所有(最大)的该未知数系数为0,说明少一个未知数,有无穷多解 for(int j=i+1;j<=n+1;++j) B[i][j]/=B[i][i]; for(int j=1;j<=n;++j) if(i!=j)//枚举所有的方程,从第j个方程中消去第i个未知数 for(int k=i+1;k<=n+1;++k)//依次把第j个方程中的第k个未知数减去应减的数值 B[j][k]-=B[j][i]*B[i][k]; } for(int i=1;i<=n;++i) x[i]=B[i][n+1]; } queue<int>q; int n,L; int child[110][6],fail[110]; bool tag[110]; void Insert(int S[],int id) { int now=0; for(int i=1;i<=L;++i) { if(!child[now][S[i]-1]) child[now][S[i]-1]=size++; now=child[now][S[i]-1]; } tag[now]=1; ma[id]=now; } void build() { fail[0]=-1; q.push(0); while(!q.empty()) { int U=q.front(); q.pop(); for(int i=0;i<6;++i) if(child[U][i]) { int V=fail[U]; while(V!=-1) { if(child[V][i]) { fail[child[U][i]]=child[V][i]; break; } V=fail[V]; } if(V==-1) fail[child[U][i]]=0; if(tag[fail[child[U][i]]]) tag[child[U][i]]=1; q.push(child[U][i]); } else if(U) child[U][i]=child[fail[U]][i]; } } void Init() { memset(child,0,sizeof(child)); memset(fail,0,sizeof(fail)); memset(tag,0,sizeof(tag)); memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); memset(x,0,sizeof(x)); memset(b,0,sizeof(b)); size=1; } int T; int main() { // freopen("hdu5955.in","r",stdin); int s[13]; scanf("%d",&T); for(;T;--T) { Init(); scanf("%d%d",&n,&L); for(int i=1;i<=n;++i) { for(int j=1;j<=L;++j) scanf("%d",&s[j]); Insert(s,i); } build(); for(int i=0;i<size;++i) { if(!tag[i]) for(int j=0;j<6;++j) A[child[i][j]+1][i+1]+=1.0/6.0; A[i+1][i+1]-=1.0; } b[1]=-1.0; guass_jordan(); for(int i=1;i<n;++i) printf("%.6lf ",x[ma[i]+1]); printf("%.6lf\n",x[ma[n]+1]); } return 0; }
【AC自动机】【高斯消元】hdu5955 Guessing the Dice Roll
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。