bzoj1444

Description

Input

注意 是0<=P

Output

Sample Input

Sample Output

HINT

 30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.

Source

要省选了 好慌啊 我什么都不会啊 只会抄答案啊 

抄了个答案 并不是很懂...

为什么我的ac自动机不对，找了个模板才对...

为什么不可以直接高斯消元啊...

先建立ac自动机，然后我们有了张trie图，trie图是由trie树和fail指针组成的。

那么我们求的就是那些单词末尾的点走到的概率。trie图是一张有向有环图，那么我们不能直接dp...就得用高斯消元解方程。

但是为什么不可以直接解啊...等待填坑 一份抄来的代码

upd:2018.2.26

再次做了一遍，当年naive

trie图本身是ac自动机的正确形式，没有trie图优化不叫ac自动机

trie图是一张有向图，自然可以用高斯消元解方程完成

可惜不能直接设概率，因为根节点已经经过，经过的概率是1，但是可能会再次经过，这样概率就大于1了。

于是我们设期望，每个点期望走过几次，这样每个节点的终止节点经过的期望次数就是概率，因为不可能经过两次一个终止节点。

那么我们可以得出方程$x_i =  x_0 * P_{0, i} + x_1 * P_{1, i} + ... + x_{cnt + 1} * P_{cnt + 1, i}$

然后解方程就好了 

#include
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n, m, l, root, size, fail;
int q[N], pos[N];
double p[N], a[N][N];
namespace ac 
{struct data {int danger, fail; int c[30];} t[N];void ins(char s[], int id){int now = root;for(int i = 0; i < l; ++i){if(!t[now].c[s[i] - 'A']) t[now].c[s[i] - 'A'] = ++size;now = t[now].c[s[i] - 'A'];}
//        printf("now=%d\n", now);t[now].danger = 1; pos[id] = now;} void get_fail(){int l = 1, r = 0;for(int i = 0; i < m; ++i) if(t[0].c[i]) q[++r] = t[0].c[i];while(l <= r) {int u=q[l++];t[u].danger |= t[t[u].fail].danger;for(int i=0; i) {int &v = t[u].c[i];if(!v) v = t[t[u].fail].c[i];else t[v].fail = t[t[u].fail].c[i], q[++r]=v;}}}
} using namespace ac;
namespace gauss 
{void build(){a[0][size + 1] = -1.0;for(int i = 0; i <= size; ++i) {a[i][i] = -1.0;if(t[i].danger) continue;for(int j = 0; j < m; ++j) {
//                printf("i=%d child=%d\n", i, t[i].c[j]);a[t[i].c[j]][i] += p[j];}}}void Gauss(){for(int now = 0; now <= size; ++now){int x = now;for(int i = now; i <= size; ++i) if(abs(a[i][now]) > abs(a[x][now]) ) x = i;for(int i = 0; i <= size + 1; ++i) swap(a[x][i], a[now][i]);double t = a[now][now];for(int i = now; i <= size + 1; ++i) a[now][i] /= t;for(int i = 0; i <= size; ++i) if(i != now){double t = a[i][now];for(int j = now; j <= size + 1; ++j) a[i][j] -= a[now][j] * t;}}}
}
int main()
{using namespace gauss;scanf("%d%d%d", &n, &l, &m);for(int i = 0; i < m; ++i) {double a, b; scanf("%lf%lf", &a, &b);p[i] = a / b; if(fabs(p[i]) < eps) ++fail;}if(fail == m) {for(int i = 1; i <= n; ++i) puts("0.00");return 0;}for(int i = 1; i <= n; ++i){char s[N]; scanf("%s", s);ins(s, i);}get_fail();build(); Gauss();for(int i = 1; i <= n; ++i) {double t = a[pos[i]][size + 1];if(fabs(t) < eps) puts("0.00"); else printf("%.2f\n", t); }return 0;
} 

转载于:https://www.cnblogs.com/19992147orz/p/6711511.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！