【HYSBZOJ】【AC自动机】【期望DP】1444 [Jsoi2009]有趣的游戏

HYSBZOJ 1444 [Jsoi2009]有趣的游戏

题目大意

◇题目传送门◆

分析

考虑我们已经得到了一个串，我们将这个串拿去和玩家的串匹配，最好的方法是用 AC 自动机：让这个串在上面跑，找到第一个有 endpos 标记的地方。

那么动态的想法就是在 AC 自动机上，设$f(i)$在第$i$个节点上停止的概率，通过 fail 指针和 Trie 树来转移，我们可以得到：

$$f(u)=\sum f(v)\times P_c$$

其中$P_c$表示$u$点表示的字符$c$生成的概率。$v$是$u$在 AC 自动机上能够走到（通过 fail 指针和 Trie 树上的边）的点。

注意的是当一个点有 endpos 标记的时候，不能转移到其他节点。

由于$f(root)$必须一开始就经过，所以我们强制定义$f(root)=\sum f(v)+1$。

参考代码

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 10;
const double EPS = 1e-6;int N, M, L;
double P[Maxn + 5];struct ACAutomaton {
    struct TrieNode {
    int endpos;TrieNode *fail;TrieNode *ch[Maxn];};TrieNode pool[Maxn * Maxn * 4 + 5];TrieNode *root, *NIL, *ncnt;int cnt;ACAutomaton () {
    NIL = ncnt = &pool[0];NIL->endpos = -1, NIL->fail = NIL;for(int i = 0; i < Maxn; i++)NIL->ch[i] = NIL;root = newnode(), cnt = 1;}TrieNode *newnode() {
    TrieNode *p = ++ncnt;p->endpos = -1, p->fail = NIL;for(int i = 0; i < Maxn; i++)p->ch[i] = NIL;cnt++;return p;}void insert(char *s, int k) {
    int lens = strlen(s);TrieNode *p = root;for(int i = 0; i < lens; i++) {
    int c = (int)s[i] - 'A';if(p->ch[c] == NIL) p->ch[c] = newnode();p = p->ch[c];}p->endpos = k;}void build() {
    queue<TrieNode *> q;for(int i = 0; i < Maxn; i++)if(root->ch[i] != NIL) {
    root->ch[i]->fail = root;q.push(root->ch[i]);}while(!q.empty()) {
    TrieNode *p = q.front();q.pop();for(int i = 0; i < Maxn; i++)if(p->ch[i] != NIL) {
    TrieNode *pre;for(pre = p->fail; pre != NIL; pre = pre->fail)if(pre->ch[i] != NIL) {
    p->ch[i]->fail = pre->ch[i];break;}if(pre == NIL) p->ch[i]->fail = root;q.push(p->ch[i]);}}}inline int getpos(TrieNode *p) {
    return p - pool;}TrieNode *findson(TrieNode *p, int c) {
    for(; p != NIL; p = p->fail)if(p->ch[c] != NIL) break;return p == NIL ? root : p->ch[c];}void prepare(double g[][Maxn * Maxn + 5]) {
    for(int i = 1; i <= cnt; i++) {
    g[i][i] = -1;if(pool[i].endpos >= 0) continue;for(int c = 0; c < M; c++) {
    TrieNode *tmp = findson(&pool[i], c);g[getpos(tmp)][i] += P[c + 1];}}g[1][cnt + 1] = -1;}
};
ACAutomaton f;double g[Maxn * Maxn + 5][Maxn * Maxn + 5];
void Gauss(int n) {
    for(int i = 1; i <= n; i++) {
    int to = i;for(; to <= n; to++)if(fabs(g[to][i]) > EPS) break;if(to > n) break;if(to != i)for(int j = 1; j <= n + 1; j++)swap(g[to][j], g[i][j]);double t = g[i][i];for(int j = 1; j <= n + 1; j++)g[i][j] /= t;for(int j = 1; j <= n; j++)if(j != i) {
    t = g[j][i];for(int k = 1; k <= n + 1; k++)g[j][k] -= t * g[i][k];}}
}double ans[Maxn + 5];
void getans() {
    for(int i = 1; i <= f.cnt; i++)if(f.pool[i].endpos >= 0)ans[f.pool[i].endpos] = g[i][f.cnt + 1];
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d %d", &N, &L, &M);for(int i = 1; i <= M; i++) {
    int x, y;scanf("%d %d", &x, &y);P[i] = 1.0 * x / y;}for(int i = 1; i <= N; i++) {
    char s[Maxn + 5];scanf("%s", s);f.insert(s, i);}f.build();f.prepare(g);Gauss(f.cnt);getans();for(int i = 1; i <= N; i++)printf("%.2f\n", ans[i] + EPS);return 0;
}