原题： http://acm.hdu.edu.cn/showproblem.php?pid=5955

题意：

摇色子，有n个人去猜最后$L$L次色子的结果，给出每个人猜的序列。色子会一直摇，直到某个人猜中，求方案数。

解析：

先来分析状态的转移，假设序列分别为：$123,231,313$123,231,313，假设当前状态为$31$31，下一次摇出$2$2时，会转移到$12$12，因为是$123$123的前缀；摇出$3$3时，$313$313猜中，就不在向下转移。

这个状态之间的转移过程可以直接用AC自动机得到$nex[31][2]=12,nex[31][3]=313$nex[31][2]=12,nex[31][3]=313。

那么怎么求解呢？每个状态，在非结束状态下，会往下转移：$to+=from*\frac{1}{6}$to+=from∗61​，这个用高斯消元求解即可。

即每个状态，都可能从其他状态转移。而定值由起始点得出，除转移到起始点以外，起始点默认有$1$1的概率。

	 1 + 1/6 x1 + 1/6 x2 + 1/6 x3 = x0 
	-->  -x0 + 1/6 x1 + 1/6 x2 + 1/6 x3 = -1

大意是这样，别人的图

代码：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
const int maxn=109;
int n,len;
int nxt[maxn][7],FAIL[maxn],edd[maxn],root,L;
int idx[maxn];
int newnode() {
    for(int i=1; i<=6; i++)
        nxt[L][i]=-1;//节点连接的边初始化为-1
    edd[L]=0;
    return L++;
}
void init() {
    L=0;
    root=newnode();
}
void insert(int *buf,int id) { //trie树的建立
    int now=root;
    for(int i=1; i<=len; i++) {
        if(nxt[now][buf[i]]==-1)
            nxt[now][buf[i]]=newnode();
        now=nxt[now][buf[i]];
    }
    edd[now]=1;
    idx[id]=now;
}

void build() { //建立ac自动机
    queue<int>que;
    for(int i=1; i<=6; i++) {
        if(nxt[root][i]==-1)
            nxt[root][i]=root;
        else {                               //若有连边则将节点加入队列 ，并将FAIL指针指向root
            FAIL[nxt[root][i]]=root;
            que.push(nxt[root][i]);
        }
    }
    while(!que.empty()) {
        int now=que.front();
        que.pop();
        for(int i=1; i<=6; i++) {
            if(nxt[now][i]==-1)
            //若无连边，则将该边指向当前节点FAIL指针指向的相应字符连接的节点
                nxt[now][i]=nxt[FAIL[now]][i];
            else { 
            //若有连边，则将儿子节点的FAIL指针指向当前节点FAIL指针指向相应字符接的节点
                FAIL[nxt[now][i]]=nxt[FAIL[now]][i];
                que.push(nxt[now][i]); //加入队列继续遍历
            }
        }
    }
}

const double EPS=1e-8;
//高斯消元，系数矩阵为a[i][j],i=1…n,j=1…n,常数为a[i][n+1],i=1…n，答案存在x[i]
double x[109], a[109][109];
double Abs(double a) {
    return a>EPS?a:-a;
}

void guass(int n) {
    for(int i=1; i<=n; i++) {
        int j = -1;
        for(int k=i; k<=n; k++) {
            if (Abs(a[k][i])>EPS) {
                j=k;
                break;
            }
        }
        if (j==-1)
            continue;
        if (i!=j)
            for(int k=i; k<=n+1; k++)
                swap(a[i][k], a[j][k]);
        for(int k=i+1; k<=n; k++) {
            double x = a[i][i], y = a[k][i];
            if (Abs(y) < EPS)
                continue;
            for(int p=i; p<=n+1; p++) {
                a[k][p] = a[i][p] - x / y * a[k][p];
            }
        }
    }
    for(int i=n; i>=1; i--) {
        double tmp = 0;
        for(int  j=i+1; j<=n; j++) {
            tmp += a[i][j] * x[j];
        }
        tmp = a[i][n+1] - tmp;
        if (Abs(a[i][i])>EPS)
            x[i] = tmp / a[i][i];
        else {

        }
    }
}

int query() {
	// 1 + 1/6 x1 + 1/6 x2 + 1/6 x3 = x0 ;
	//--》  -x0 + 1/6 x1 + 1/6 x2 + 1/6 x3 = -1；
    memset(a,0,sizeof a);
    memset(x,0,sizeof x);
    for(int i=0; i<L; i++) {
        a[i+1][i+1]=-1;
    }
    a[0+1][L+1]=-1;
    for(int i=0; i<L; i++) {
        if(edd[i])
            continue;
        for(int j=1; j<=6; j++) {
            a[nxt[i][j]+1][i+1]+=1.0/6;
        }
    }
    guass(L);
    for(int i=1; i<=n; i++) {
        printf("%6f%c",x[idx[i]+1],(i==n?'\n':' '));
    }
}

int buf[maxn];
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&len);
        init();
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=len; j++) {
                scanf("%d",buf+j);
            }
            insert(buf,i);
        }
        build();
        query();
    }
}