Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 [Jsoi2009]有趣的游戏 [AC自动机, 矩阵, DP]

Posted on In

APIO和CTSC一个都去不了太真实了

其实能去才奇怪吧←_←

如果进不了R2还得去APIO似乎更惨一下啊←_←

懵逼的题目

BZOJ

扯淡的 题解

把上面那个题的KMP换成AC自动机就行了

注意因为要"保留贡献"

所以单词的结尾节点在矩阵中要置为1

沙茶的 代码

我居然一遍写对了

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
/**************************************************************
    Problem: 1444
    User: Cansult
    Language: C++
    Result: Accepted
    Time:796 ms
    Memory:12492 kb
****************************************************************/
 
// 把那个题的dp改成概率dp是不是就行了
// 一直到当前的影响小于eps?
// 设f[i][j]: 当前已经进行了i次, 在第j个节点, 还未决出胜负的概率
// 对于下一个节点: 如果能结束游戏就结束 然后算出贡献; 否则到f值小于eps时结束
// 还得整矩阵 高消是不存在的
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (100)
#define MAXS (11)
#define DXG (10000000000000ll + 5)
#define LL long long
#define DD double
#define pii pair<int, int>
using namespace std;
struct node {
    int son[MAXS], fail, bh;
} b[MAXN << 5];
struct matrix {
    int n, m;
    DD zh[MAXN][MAXN];
    matrix() { memset(zh, 0, sizeof(zh)); }
} m1, ma, f;
int n, l, m, cntb;
pii mb[MAXN];
char s[MAXN][MAXN];
DD ans[MAXN];
matrix tim(matrix x, matrix y) {
    matrix re;
    re.n = x.n, re.m = y.m;
    for (int i = 0; i < re.n; i++)
        for (int j = 0; j < re.m; j++) 
            for (int k = 0; k < x.m; k++)
                re.zh[i][j] += x.zh[i][k] * y.zh[k][j];
    return re;
}
matrix ksm(LL b) {
    if (!b) return m1;
    matrix re = ksm(b >> 1);
    re = tim(re, re);
    if (b & 1) re = tim(re, ma);
    return re;
}
void initac() {
    queue<int> q;
    for (int i = 0; i < MAXS; i++) if (b[0].son[i]) q.push(b[0].son[i]);
    while (!q.empty()) {
        int dq = q.front();
        q.pop();
        for (int i = 0; i < MAXS; i++)
            if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
            else b[dq].son[i] = b[b[dq].fail].son[i];
    }
}
int pd(int x) {
    for (; x; x = b[x].fail)
        if (b[x].bh)
            return b[x].bh;
    return 0;
}
void init() {
    initac();
    m1.n = m1.m = cntb;
    for (int i = 0; i < cntb; i++) m1.zh[i][i] = 1;
    f.n = 1, f.m = cntb;
    f.zh[0][0] = 1;
    ma.n = ma.m = cntb;
    for (int i = 0; i < cntb; i++)
        if (!pd(i))
            for (int j = 0; j < m; j++)
                ma.zh[i][b[i].son[j]] += (DD)mb[j].first / mb[j].second;
        else ma.zh[i][i] = 1; // 就是这个地方 如果不赋为1的话之前的工作就白做了
}
int main() {
    scanf("%d%d%d", &n, &l, &m);
    for (int i = 0; i < m; i++) scanf("%d%d", &mb[i].first, &mb[i].second);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i]);
        int dq = 0;
        for (int j = 0, ndq; j < strlen(s[i]); j++) {
            ndq = s[i][j] - 'A';
            if (!b[dq].son[ndq]) b[dq].son[ndq] = ++cntb;
            dq = b[dq].son[ndq];
        }
        b[dq].bh = i;
    }
    ++cntb;
    init();
    f = tim(f, ksm(DXG));
    for (int i = 1; i < cntb; i++) ans[pd(i)] += f.zh[0][i];
    for (int i = 1; i <= n; i++) printf("%.2lf\n", ans[i]);
    return 0;
}

By 准备退役旅游的 Cansult