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，他也应该作为根节点初始时的概率放在右边。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<set>
  9 using namespace std;
 10 typedef long long LL;
 11 #define N 100010
 12 #define pi 3.1415926535
 13 
 14 int n, l, t;
 15 const int maxn = 105;
 16 struct trie{
 17     int son[7];
 18     int ed;
 19     int fail;
 20 }AC[maxn];
 21 int tot = 0;
 22 int fp[11];
 23 
 24 void build(int s[], int id)
 25 {
 26     int now = 0;
 27     for(int i = 0; i < l; i++){
 28         if(AC[now].son[s[i]] == 0){
 29             AC[now].son[s[i]] = ++tot;
 30         }
 31         now = AC[now].son[s[i]];
 32     }
 33     AC[now].ed = id;
 34     fp[id] = now;
 35 }
 36 
 37 void get_fail()
 38 {
 39     queue<int>que;
 40     for(int i = 1; i <= 6; i++){
 41         if(AC[0].son[i] != 0){
 42             AC[AC[0].son[i]].fail = 0;
 43             que.push(AC[0].son[i]);
 44         }
 45     }
 46 
 47     while(!que.empty()){
 48         int u = que.front();
 49         que.pop();
 50         for(int i = 1; i <= 6; i++){
 51             if(AC[u].son[i] != 0){
 52                 AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];
 53                 que.push(AC[u].son[i]);
 54             }
 55             else{
 56                 AC[u].son[i] = AC[AC[u].fail].son[i];
 57             }
 58         }
 59     }
 60 }
 61 
 62 double a[maxn][maxn], x[maxn];
 63 const double eps = 1e-10;
 64 int equ, var;
 65 void gauss()
 66 {
 67     equ = var = tot + 1;
 68     int i,j,k,col,max_r;
 69     for(k=0,col=0;k<equ&&col<var;k++,col++)
 70     {
 71         max_r=k;
 72         for(i=k+1;i<equ;i++)
 73         {
 74             if(fabs(a[i][col] )>fabs(a[max_r][col] ) ) max_r=i;
 75         }
 76         if(fabs(a[max_r][col])<eps )  return;
 77         if(k!=max_r)
 78         {
 79             for(j=col;j<=var;j++)  swap(a[k][j],a[max_r][j]  );
 80         }
 81         for(j=col+1;j<=var;j++)  a[k][j]/=a[k][col];
 82 
 83         a[k][col]=1;
 84 
 85         for(i=0;i<equ;i++) if(i!=k)
 86         {
 87             for(j=col+1;j<=var;j++) a[i][j]-=a[k][j]*a[i][col];
 88 
 89             a[i][col]=0;
 90         }
 91     }
 92     for(i=0;i<equ;i++)  x[i]=a[i][var];
 93     return;
 94 }
 95 
 96 int main()
 97 {
 98     scanf("%d", &t);
 99     while(t--){
100         for(int i = 0; i <= tot; i++){
101             AC[i].fail = 0;
102             AC[i].ed = 0;
103             for(int j = 0; j < 7; j++){
104                 AC[i].son[j] = 0;
105             }
106         }
107         tot = 0;
108 
109         scanf("%d%d", &n, &l);
110         for(int i = 1; i <= n; i++){
111             int tmp[11];
112             for(int j = 0; j < l; j++){
113                 scanf("%d", &tmp[j]);
114             }
115             build(tmp, i);
116         }
117         get_fail();
118 
119         memset(a, 0, sizeof(a));
120         memset(x, 0, sizeof(x));
121         for(int i = 0; i <= tot; i++)a[i][i] = -1.0;
122         for(int i = 0; i <= tot; i++){
123             if(AC[i].ed == 0){
124                 for(int j = 1; j <= 6; j++){
125                     int to = AC[i].son[j];
126                     a[to][i] += 1.0 / 6;
127                 }
128             }
129 
130         }
131 
132         a[0][tot + 1] = -1.0;//虚拟节点
133         gauss();
134         for(int i = 1; i <= n; i++){
135             printf("%.6f", x[fp[i]]);
136             if(i == n){
137                 printf("
");
138             }
139             else{
140                 printf(" ");
141             }
142         }
143 
144         //cout<<"yes"<<endl;
145     }
146 
147     return 0;
148 }