HDU 5955 Guessing the Dice Roll

超、凢脫俗 2021-10-23 09:41 145阅读 0赞

### HDU 5955 Guessing the Dice Roll ###

**2016 ACM/ICPC 亚洲区沈阳站**

#### 题意 ####

*  有\\(N\\le 10\\)个人，每个猜一个长度为\\(L \\le 10\\)的由\\(1-6\\)构成的序列，保证序列两两不同。
 *  不断地掷骰子，直到后缀与某人的序列匹配，则对应的人获胜。
 *  求每个人获胜的概率。

#### 思路 ####

*  显然，涉及的序列最多100个，用**ac自动机**构出这些状态，计算状态之间的转移概率。
 *  记增量矩阵为\\(A\\)（即终状态不再计算转移到自身的概率），答案为\\(b\\)，初始序列为\\(x\\)，则\\\[b=\\sum\_\{i=1\}^\{\\infty\}\{A^i\}x\\\]
 *  显然矩阵\\(A\\)是收敛的，所以式子转化为\\\[b=(I-A)^\{-1\}x\\\\x=(I-A)b\\\]
 *  **高斯消元**求解即可，注意精度问题。
 *  另一种解法，构造包括终止状态转移到自身的矩阵，结合快速幂，可以卡过去（注意指数取\\(2^i\\)形式以减少常数）。

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define sz(x) ((int)(x).size()) #define rep(i,l,r) for(int i=(l);i<(r);++i) //-------head------- const int N = 1007; const double EPS = 1e-12; int n, l, a[N], id[N]; template<int V> struct AhoCorasick { int dep[V]; int siz, lnk[V], que[V], trie[V][7]; int addNode(int _dep) { memset(trie[siz], 0, sizeof(trie[siz])); lnk[siz] = 0, dep[siz] = _dep; return siz++; } void init() { siz = 0; addNode(0); } int add(const int *a, int n) { int p = 0; rep(i, 0, n) { int x = a[i]; if (!trie[p][x]) trie[p][x] = addNode(i + 1); p = trie[p][x]; } return p; } void build() { que[0] = 0; for (int h = 0, t = 1; h < t; ++h) { int v = que[h]; rep(c, 1, 7) if (trie[v][c]) { int u = lnk[v]; while (u && !trie[u][c]) u = lnk[u]; lnk[trie[v][c]] = !v ? 0 : trie[u][c]; que[t++] = trie[v][c]; } else { trie[v][c] = trie[lnk[v]][c]; } } } }; template<int N> struct Gauss { double a[N][N]; void init(int n, int m) { rep(i, 0, n) rep(j, 0, m) a[i][j] = 0; } void run(int n, int m) { int row, col; for (row = col = 0; row < n && col < m; ++row, ++col) { int mxr = row; rep(i, row + 1, n) if (fabs(a[i][col]) > fabs(a[mxr][col])) mxr = i; if (fabs(a[mxr][col]) < EPS) { --row; continue; } if (mxr != row) swap(a[row], a[mxr]), swap(id[row], id[mxr]); rep(i, 0, n) if (i != row && fabs(a[i][col]) > EPS) for (int j = m; j >= col; --j) a[i][j] -= a[row][j] * a[i][col] / a[row][col]; } } void out(int n, int m) { rep(i, 0, n) { rep(j, 0, m) printf("%lf ", a[i][j]); puts(""); } } }; AhoCorasick<N> ac; Gauss<N> ga; double ans[N]; int main() { int T; scanf("%d", &T); rep(cas, 0, T) { scanf("%d%d", &n, &l); ac.init(); memset(id, -1, sizeof(id)); rep(i, 0, n) { rep(j, 0, l) scanf("%d", &a[j]); id[ac.add(a, l)] = i; } ac.build(); ga.init(ac.siz, ac.siz + 1); rep(i, 0, ac.siz) { if (~id[i]) { // ga.a[i][i] = 0; } else { rep(j, 1, 7) ga.a[ac.trie[i][j]][i] += 1.0 / 6.0 ; } } rep(i, 0, ac.siz) ga.a[i][i] -= 1.0; ga.a[0][ac.siz] = -1.0; // ga.out(ac.siz, ac.siz + 1); ga.run(ac.siz, ac.siz); // puts(""); // ga.out(ac.siz, ac.siz + 1); rep(i, 0, ac.siz) if (~id[i]) { ans[id[i]] = ga.a[i][ac.siz] / ga.a[i][i]; } rep(i, 0, n) { if (i) putchar(' '); printf("%.6lf", fabs(ans[i])); } puts(""); } return 0; }

转载于:https://www.cnblogs.com/mcginn/p/6021336.html