HDU 5955 gauss概率dp+ac自动机

川长思鸟来 2022-05-08 10:52 210阅读 0赞

题意：有n个人，每个人猜一个\[1,6\]长度为L的序列，然后无限制的掷骰子，先掷到的那个序列，那个人就是winner，

问每个人赢得概率。

思路：骰子是掷无限次的，但是有许多状态是重复的，每一种掷法最终必定是以某一个人的序列结束的，

也就是说，谁都不赢的序列是无穷的，概率趋近于0，所以每个人概率相加是1.

我们可以用ac自动机节点编号当做某种情况的状态，nxt数组就是这个状态转向的下个状态。

这样构造出转移方程就是

dp\[i\]=sum(dp\[from\]); dp\[i\]是i状态的概率。

最多100个状态，gauss求解。

注意，终止态不转移到任何节点

#include<bits/stdc++.h>
    using namespace std;
    
    int nxt[500010][7], fail[500010], ed[500010], L, id[110];
    struct Trie{
        int root;
        int newnode(){
            for(int i=1; i<=6; i++)
                nxt[L][i]=-1;
            ed[L++]=0;
            return L-1;
        }
    
        void init(){
            L=0;
            root=newnode();
        }
        void Insert(int buf[], int ii, int len){
            int now=root;
            for(int i=0; i<len; i++){
                int v=buf[i];
                if(nxt[now][v]==-1)
                    nxt[now][v]=newnode();
                now=nxt[now][v];
            }
            id[ii]=now;
            ed[now]++;
        }
        void build(){
            queue<int> Q;
            fail[root]=root;
            for(int i=1; i<=6; i++){
                if(nxt[root][i]==-1)
                    nxt[root][i]=root;
                else{
                    fail[nxt[root][i]]=root;
                    Q.push(nxt[root][i]);
                }
            }
            while(!Q.empty()){
                int now=Q.front();
                Q.pop();
                for(int i=1; i<=6; i++)
                    if(nxt[now][i]==-1)
                        nxt[now][i]=nxt[fail[now]][i];
                    else{
                        fail[nxt[now][i]]=nxt[fail[now]][i];
                        Q.push(nxt[now][i]);
                    }
            }
        }
    }ac;
    const int N=110;
    double a[N][N], x[N];
    int equ, var;
    const double eps=1e-10;
    
    
    int gauss(){
        int i, j, k, col, max_r;
        for(k=0, col=0; k<equ&&col<var; k++, col++){
            max_r=k;
            for(i=k+1; i<equ; i++)
                if(fabs(a[i][col])>fabs(a[max_r][col]))
                    max_r=i;
    
            if(fabs(a[max_r][col])<eps) return 0;
            if(k!=max_r){
                for(j=col; j<var; j++)
                    swap(a[k][j], a[max_r][j]);
                swap(x[k], x[max_r]);
            }
            x[k]/=a[k][col];
            for(j=col+1; j<var; j++) a[k][j]/=a[k][col];
            a[k][col]=1;
            for(i=0;i<equ; i++)
            if(i!=k){
                x[i]-=x[k]*a[i][col];
                for(j=col+1; j<var; j++) a[i][j]-=a[k][j]*a[i][col];
                a[i][col]=0;
            }
        }
        return 1;
    }
    int s[20];
    
    int main(){
        int T, n, m;
        scanf("%d", &T);
        while(T--){
            memset(x, 0, sizeof x);
            memset(a, 0, sizeof a);
            scanf("%d%d", &n, &m);
            ac.init();
            for(int i=1; i<=n; i++){
                for(int j=0; j<m; j++)
                    scanf("%d", s+j);
                ac.Insert(s, i, m);
            }
            ac.build();
            x[0]=-1;
            for(int i=0; i<L; i++){
                a[i][i]=-1;
                if(ed[i]) continue;
                for(int j=1; j<=6; j++){
                    a[nxt[i][j]][i]+=1./6;
                }
            }
            var=equ=L;
            gauss();
            for(int i=1; i<n; i++){
                printf("%.6lf ", x[id[i]]);
            }
            printf("%.6lf\n", x[id[n]]);
        }
        return 0;
    }