【HDOJ5955】Guessing the Dice Roll（概率DP，AC自动机，高斯消元）

题意：

有n个人，每个人有一个长为L的由1~6组成的数串，现在扔一个骰子，依次记录扔出的数字，如果当前扔出的最后L个数字与某个人的数串匹配，那么这个人就算获胜，现在问每个人获胜的概率是多少。

n,l<=10

思路：对于无限型的概率

首先显然有一个暴力做法是对于n个串建出AC自动机和转移矩阵后跑若干次矩乘快速幂DP使得答案趋于稳定后可以将结果看做答案

正解是高斯消元

每个点对于它的后继有1/6的概率跑到，计算贡献后累加

边界条件：题目给出的n个串没有后继

游戏开始时必定会转移到根节点，等价于有一个虚的节点（不需要建立方程）对根有100%的1的贡献

剩下的就是高斯消元模板了

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second 
#define MP make_pair
#define N  11000
#define M  210
#define MOD 1000000007
#define eps 1e-8 
#define pi acos(-1)

double a[M][M];
int nxt[M][7],fa[M],c[M],d[N],q[N],b[N],flag[N],n,l,cnt;

int read()
{ 
   int v=0,f=1;
   char c=getchar();
   while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
   while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
   return v*f;
}

void build(int k)
{
    int u=1;
    for(int i=1;i<=l;i++)
    {
        if(!nxt[u][b[i]]) nxt[u][b[i]]=++cnt;
        u=nxt[u][b[i]];
    }
    c[k]=u;
    d[u]=k;
}
            
void acauto()
{
    int t=0; int w=1; q[1]=1;
    while(t<w)
    {
        int u=q[++t];
    //    printf("%d
",u); 
        for(int i=1;i<=6;i++)
        {
             if(nxt[u][i])
              {
                 int son=nxt[u][i];        
                 int p=fa[u];
                 if(u==1) fa[son]=1;
                  else fa[son]=nxt[p][i];
                 q[++w]=son;
             }
              else
              {
                  int p=fa[u];
                if(u==1) nxt[u][i]=1;
                 else nxt[u][i]=nxt[p][i];
               }
        }
    }
}

void init()
{
/*    for(int i=1;i<=cnt;i++)
    {
        fa[i]=flag[i]=d[i]=0;
        for(int j=1;i<=6;j++) nxt[i][j]=0;
    }
    memset(q,0,sizeof(q));
    for(int i=1;i<=cnt;i++)
     for(int j=0;j<=cnt;j++) a[i][j]=0;
    for(int i=1;i<=n;i++) c[i]=0;*/
    memset(a,0,sizeof(a));
    memset(nxt,0,sizeof(nxt));
    memset(fa,0,sizeof(fa));
    memset(c,0,sizeof(c));
    memset(d,0,sizeof(d));
    //memset(q,0,sizeof(q));
    memset(b,0,sizeof(b));
    cnt=1;
}

void test()
{
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=cnt+1;j++) printf("%.2lf ",a[i][j]);
        printf("
");
    }
    printf("
");
}

int main()
{
    freopen("hdoj5955.in","r",stdin);
    freopen("hdoj5955.out","w",stdout);
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        init();
        scanf("%d%d",&n,&l);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=l;j++) scanf("%d",&b[j]);
            build(i);
        }
        
        acauto();
        
        for(int i=1;i<=cnt;i++)
        {
            a[i][cnt+1]=0; 
            a[i][i]=-1.0;
            if(d[i]) continue;
            for(int j=1;j<=6;j++)
            {
                int v=nxt[i][j];
                a[v][i]+=1.0/6.0;
            //    printf("%d %d
",i,v);
            }
        }
        
        a[1][cnt+1]=-1.0;
        
    //    test();

        for(int i=1;i<=cnt;i++)
        {
            int K=i;
            for(int j=i+1;j<=cnt;j++)
             if(fabs(a[j][i])>fabs(a[K][i])) K=j;
             
            if(K!=i)
             for(int j=1;j<=cnt+1;j++) swap(a[i][j],a[K][j]);
            
            for(int j=i+1;j<=cnt;j++)
            {
                double f=a[j][i]/a[i][i];
                for(int k=i;k<=cnt+1;k++) a[j][k]-=f*a[i][k];
            } 
        
            
        }
        
        for(int i=cnt;i>=1;i--)
        {
             for(int j=i+1;j<=cnt;j++) 
              a[i][cnt+1]-=a[i][j]*a[j][cnt+1];
             a[i][cnt+1]=a[i][cnt+1]/a[i][i];
        }
        
    //    test();
        for(int i=1;i<=n;i++) 
         if(i<n) printf("%.6lf ",a[c[i]][cnt+1]);
          else printf("%.6lf
",a[c[i]][cnt+1]);
        
    }

    return 0;
}