题意：有一个6面的骰子，有n个人每个人猜了一个长度为l的序列，不停的掷骰子直到满足一个人的序列则那个人获胜，求每个人获胜的概率。
先根据n个序列构建ac自动机
然后根据trie图建立方程组 :
对于不是 tag结点的状态节点i，可以转移到其6个后继节点j，那么就在方程 A【j】【i】+=1/6（第j行表示关于状态j的方程，第j行第i列表示i能有多少概率转移过来状态j）
然后自己应该在方程的等号右边，直接令A【j】【j】+=-1即可，最右边默认为0即可。
只有根节点有点特殊
可以看作有一个虚拟节点，一开始就以1的概率转移到根节点
因此X[0]=-1
（此模版X【0】相当于方程组的等号右边常数值）
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;const int maxlen=1000+50;
const int maxn=120;
const int all_size=6;
int trie[maxn][all_size];
int fail[maxn];
int tag[maxn];
int fp[10];
int L,n;
int sz;
queue<int >Q;
struct Aho
{int root;int newnode()//静态创建新节点{memset(trie[sz],-1,sizeof trie[sz]);tag[sz]=0;sz++;return sz-1;}void init()//初始化{sz=0;newnode();}void insert(int s[],int id) //插入字符串构建ac自动机，构建trie树{int len=L,p=0;for (int i=0; i<len; i++){int id=s[i]-1;if (trie[p][id]==-1)trie[p][id]=newnode();p=trie[p][id];}tag[p]=id; //结束标记fp[id]=p;}void getfail() //构建自动机fail指针{while(!Q.empty()) Q.pop();fail[root]=root; //root指向rootfor (int i=0; i<all_size; i++){if (trie[root][i]==-1)//第一个字符不存在，指向roottrie[root][i]=root;else //第一个字符的fail指针指向root{fail[trie[root][i]]=root;Q.push(trie[root][i]); //并放入队列，待bfs扩展}}while(!Q.empty()){int u=Q.front(); //取扩展节点Q.pop();// if (tag[u]||tag[fail[u]]) continue;if(tag[fail[u]]) tag[u]=tag[fail[u]]; //***如果之前是tag，直接标记for (int i=0; i<all_size; i++)//遍历所有子节点{if (trie[u][i]==-1)//如果不存在，则子节点直接指向fail[u]节点的对应子节点trie[u][i]=trie[fail[u]][i];else //如果存在，则该节点的fail指针指向fail[u]节点对应的子节点{fail[trie[u][i]]=trie[fail[u]][i];Q.push(trie[u][i]); //继续扩展}}}}} aho;#define eps 1e-6
const int MAXN=120;
double a[MAXN][MAXN],x[MAXN];
int equ,var;
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(int i = 0; i < equ; i++)if(i != k){x[i] -= x[k]*a[i][k];for(j = col+1; j < var; j++)a[i][j] -= a[k][j]*a[i][col];a[i][col] = 0;}}return 1;
}void init_guass(int n, int m)
{memset(x, 0, sizeof(x));memset(a, 0, sizeof(a));var=n,equ=m;
}//********guassint son[120];
void out()
{for (int i=0; i<sz; i++){for (int j=0; j<sz; j++){printf("%lf ",a[i][j]);}printf("%lf\n",x[i]);}
}void build_nmb() //建立方程组
{init_guass(sz,sz);for (int i=0; i<sz; i++){if (!tag[i])for (int j=0; j<all_size; j++){a[trie[i][j]][i]+=1.0/6;}a[i][i]+=-1;}
// a[0][sz]=-1;x[0]+=-1; //虚拟节点以1的概率转移到节点0
}
int name[15][15];
const long long inf=1e9;
int main()
{int cnt=1;int t;cin>>t;while(t--){cin>>n>>L;aho.init();for (int i=0; i<n; i++){for (int j=0; j<L; j++)scanf("%d",&name[i][j]);aho.insert(name[i],i+1);}aho.getfail();init_guass(sz,sz);build_nmb();// gauss();int ret=Gauss();for (int i=1; i<=n; i++){if (i>1)printf(" ");printf("%.6f",x[fp[i]]);}printf("\n");}return 0;
}