Guessing the Dice Roll

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1632 Accepted Submission(s): 480

Problem Description

There are N players playing a guessing game. Each player guesses a sequence consists of {1,2,3,4,5,6} with length L, then a dice will be rolled again and again and the roll out sequence will be recorded. The player whose guessing sequence first matches the last L rolls of the dice wins the game.

Input

The first line is the number of test cases. For each test case, the first line contains 2 integers N (1 ≤ N ≤ 10) and L (1 ≤ L ≤ 10). Each of the following N lines contains a guessing sequence with length L. It is guaranteed that the guessing sequences are consist of {1,2,3,4,5,6} and all the guessing sequences are distinct.

Output

For each test case, output a line containing the winning probability of each player with the precision of 6 digits.

Sample Input

3
5 1
1
2
3
4
5
6 2
1 1
2 1
3 1
4 1
5 1
6 1
4 3
1 2 3
2 3 4
3 4 5
4 5 6

Sample Output

0.200000 0.200000 0.200000 0.200000
0.200000
0.027778 0.194444 0.194444 0.194444
0.194444 0.194444
0.285337 0.237781 0.237781 0.239102

Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

Recommend

jiangzijing2015

题意：

有n个人猜掷骰子的序列。给定序列长度是l。只要n个人中的一个序列出现了，这个人就赢了游戏结束。问他们获胜的概率是多少。

思路：

没有想到是AC自动机。但是其实他本质就是在一个自动机的不同状态之间转转转，看最后转到哪个状态上去。

对这几个序列建立了AC自动机之后，就可以列出他们互相之间转移的概率方程了。然后解方程就可以得到每个人获胜的概率。

矩阵中的第\(j\)行表示的就是关于\(j\)这个状态的方程。\(a[j][i]\)表示由状态\(i\)转移到状态\(j\)的概率。

\(a[i][i]\)本身应该放在方程的右边，所以他是\(-1\)

根节点是比较特殊的，我们需要再设置一个虚拟节点，虚拟节点到根节点的概率是1，他也应该作为根节点初始时的概率放在右边。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<set>

 using namespace std;

 typedef long long LL;

 #define N 100010

 #define pi 3.1415926535

 int n, l, t;

 const int maxn = ;

 struct trie{

     int son[];

     int ed;

     int fail;

 }AC[maxn];

 int tot = ;

 int fp[];

 void build(int s[], int id)

 {

     int now = ;

     for(int i = ; i < l; i++){

         if(AC[now].son[s[i]] == ){

             AC[now].son[s[i]] = ++tot;

         }

         now = AC[now].son[s[i]];

     }

     AC[now].ed = id;

     fp[id] = now;

 }

 void get_fail()

 {

     queue<int>que;

     for(int i = ; i <= ; i++){

         if(AC[].son[i] != ){

             AC[AC[].son[i]].fail = ;

             que.push(AC[].son[i]);

         }

     }

     while(!que.empty()){

         int u = que.front();

         que.pop();

         for(int i = ; i <= ; i++){

             if(AC[u].son[i] != ){

                 AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];

                 que.push(AC[u].son[i]);

             }

             else{

                 AC[u].son[i] = AC[AC[u].fail].son[i];

             }

         }

     }

 }

 double a[maxn][maxn], x[maxn];

 const double eps = 1e-;

 int equ, var;

 void gauss()

 {

     equ = var = tot + ;

     int i,j,k,col,max_r;

     for(k=,col=;k<equ&&col<var;k++,col++)

     {

         max_r=k;

         for(i=k+;i<equ;i++)

         {

             if(fabs(a[i][col] )>fabs(a[max_r][col] ) ) max_r=i;

         }

         if(fabs(a[max_r][col])<eps )  return;

         if(k!=max_r)

         {

             for(j=col;j<=var;j++)  swap(a[k][j],a[max_r][j]  );

         }

         for(j=col+;j<=var;j++)  a[k][j]/=a[k][col];

         a[k][col]=;

         for(i=;i<equ;i++) if(i!=k)

         {

             for(j=col+;j<=var;j++) a[i][j]-=a[k][j]*a[i][col];

             a[i][col]=;

         }

     }

     for(i=;i<equ;i++)  x[i]=a[i][var];

     return;

 }

 int main()

 {

     scanf("%d", &t);

     while(t--){

         for(int i = ; i <= tot; i++){

             AC[i].fail = ;

             AC[i].ed = ;

             for(int j = ; j < ; j++){

                 AC[i].son[j] = ;

             }

         }

         tot = ;

         scanf("%d%d", &n, &l);

         for(int i = ; i <= n; i++){

             int tmp[];

             for(int j = ; j < l; j++){

                 scanf("%d", &tmp[j]);

             }

             build(tmp, i);

         }

         get_fail();

         memset(a, , sizeof(a));

         memset(x, , sizeof(x));

         for(int i = ; i <= tot; i++)a[i][i] = -1.0;

         for(int i = ; i <= tot; i++){

             if(AC[i].ed == ){

                 for(int j = ; j <= ; j++){

                     int to = AC[i].son[j];

                     a[to][i] += 1.0 / ;

                 }

             }

         }

         a[][tot + ] = -1.0;//虚拟节点

         gauss();

         for(int i = ; i <= n; i++){

             printf("%.6f", x[fp[i]]);

             if(i == n){

                 printf("\n");

             }

             else{

                 printf(" ");

             }

         }

         //cout<<"yes"<<endl;

     }

     return ;

 }

hdu5955 Guessing the Dice Roll【AC自动机】【高斯消元】【概率】

Guessing the Dice Roll