Guessing the Dice Roll
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1209 Accepted Submission(s): 352
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
题目链接：HDU 5955
跟以前做过的挑战程序设计那本上的题目有点像传送门，这题是求概率，那题是求期望，反正都是写出公式，然后列出方程，得到系数矩阵再用高斯消元求答案。
这题只能从非结束节点上转移过去，因此有：$p_v= {1 \over 6} * \sum{p_u}$，其中$u$是非结束节点，然后$p_0=1$，因为走到根节点是必需的。
然后用题目中的串构建$AC$自动机再根据上面的节点转移即可。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
struct Trie
{
int nxt[7], fail, v;
void init()
{
for (int i = 0; i <= 6; ++i)
nxt[i] = -1;
fail = v = 0;
}
} L[N];
int sz;
int n, l;
double A[N][N], ans[N];
int pos[N];
int s[11];
void init()
{
sz = 0;
L[sz++].init();
CLR(A, 0);
CLR(ans, 0);
}
inline int newnode()
{
L[sz].init();
return sz++;
}
void ins(int s[], int id, int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
if (L[u].nxt[s[i]] == -1)
L[u].nxt[s[i]] = newnode();
u = L[u].nxt[s[i]];
}
L[u].v = 1;
pos[id] = u;
}
void build()
{
L[0].fail = 0;
queue<int>Q;
for (int i = 1; i <= 6; ++i)
{
int &v = L[0].nxt[i];
if (~v)
{
Q.push(v);
L[v].fail = 0;
}
else
v = 0;
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
int uf = L[u].fail;
L[u].v |= L[uf].v;
for (int i = 1; i <= 6; ++i)
{
int &v = L[u].nxt[i];
if (~v)
{
Q.push(v);
L[v].fail = L[uf].nxt[i];
}
else
v = L[uf].nxt[i];
}
}
}
void Gauss(int ne, int nv)
{
int i, j ;
for (int ce = 0, cv = 0; cv < ne && cv < nv; ++ce, ++cv)
{
int te = ce;
for (i = ce; i < ne; ++i)
if (fabs(A[i][cv]) > fabs(A[te][cv]))
te = i;
if (te != ce)
{
for (j = cv; j <= nv; ++j)
swap(A[ce][j], A[te][j]);
}
double bas = A[ce][cv];
for (j = cv; j <= nv; ++j)
A[ce][j] /= bas;
for (i = ce + 1; i < ne; ++i)
{
for (int j = cv + 1; j <= nv; ++j)
A[i][j] -= A[i][cv] * A[ce][j];
}
}
for (i = ne - 1; i >= 0; --i)
{
ans[i] = A[i][nv];
for (j = i + 1; j < nv; ++j)
ans[i] -= ans[j] * A[i][j];
ans[i] /= A[i][i];
}
}
int main(void)
{
int TC, i, j;
scanf("%d", &TC);
while (TC--)
{
init();
scanf("%d%d", &n, &l);
for (i = 1; i <= n; ++i)
{
for (j = 0; j < l; ++j)
scanf("%d", &s[j]);
ins(s, i, l);
}
build();
A[0][sz] = -1;
A[0][0] = -1;
const double P = 1.0 / 6.0;
for (i = 0; i < sz; ++i)
{
A[i][i] = -1;
if (L[i].v)
continue;
for (j = 1; j <= 6; ++j)
{
int v = L[i].nxt[j];
A[v][i] += P;
}
}
Gauss(sz, sz);
for (i = 1; i <= n; ++i)
printf("%.6f%c", ans[pos[i]], " \n"[i == n]);
}
return 0;
}