JSOI 2009 BZOJ 1444 有趣的游戲

題面

題目描述

小陽陽發明了一個有趣的游戲：有n個玩家，每一個玩家均有一個長度為 l 的字母序列，任何兩個玩家的字母序列不同。共有m種不同的字母，所有的字母序列都由這m種字母構成，為了方便，我們取大寫字母的前。個字母。例如。m =3 , l = 4 , ABAA , CBCA 為兩個合法的字母序列。現在由小陽陽來操控一臺神奇的機器，每個時刻機器會隨機產生一個字母，其中第i種字母隨機出來的概率為pi/qi，顯然 sum(pi/qi)=1 。這樣T個時刻后機器會產生一個長度為 T 的字母序列。如果某個時刻某個玩家發現自己的字母序列在機器產生的字母序列中出現了，“出現”的定義是玩家的字母序列是機器產生的字母序列中連續的一段，那么我們稱這個玩家獲勝，游戲結束。現在小陽陽感興趣的一個問題是，每個玩家分別有多大的概率能獲得這場游戲的勝利呢？

輸入格式

第一行有三個正整數n，l，m表示有n個人，每個人的字母序列長度為l，共有m個字母。
接下來m行，每行有兩個非負整數p，q，表示隨機到第i個字母的概率為p/q（0<=p<=q<=10，（p，q）=1）。數據保證m個字母的隨機概率之和為1。
接下來n行，每行有一個長度為l的字母序列，表示第i個人的字母序列。數據保證所有的字母為大寫字母的前m個且沒有兩個字母序列完全相同。

輸出格式

包含n行，每行包含一個實數，表示第i個人獲勝的概率，輸出結果四舍五入到兩位小數。

樣例輸入1

3 2 2
1 2
1 2
AB
BA
AA

樣例輸出1

0.25
0.50
0.25

樣例輸入2

3 4 2
1 2
1 2
AABA
ABAA
BAAA

樣例輸出2

0.31
0.33
0.37

樣例說明1

兩種字母 A 和 B ，概率均為 1/2。若前兩個字母為 AB , BA 或AA，均有一個人獲勝，獲勝概率為 1 / 4 ；若前兩個字母為 BB ，那么之后隨機到 BBA , BBBA , BBBB 入都一定是 BA 獲勝。因此 BA 的獲勝概率為 1/4 + 1/4 = 1/2 。

樣例說明 2

三個人的獲勝概率分別為 4/13 , 17/52 , 19/52 ，注意輸出結果四舍五入到兩位小數。、

數據范圍

100%的數據保證, n , l, m≤ 10.

題解

涉及概率 / 期望的題, 無非就是概率轉期望, 期望轉概率, DP一下就好了.
比如說這一題, 我們只需要建立trie圖, 求出每個節點的經過的期望次數即可.
注意, 當一個節點的兒子為NULL時, 應該把這個概率加到根節點上.

#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>const int N = 10, M = 10, L = 10;
int n, l, m;
double p[M];
struct matrix
{int n;double a[N * L][N * L + 1];inline matrix(){memset(a, 0, sizeof(a));}inline void gauss(){for(int i = 0; i < n; ++ i){int p;for(p = i; p < n && a[p][i] == 0; ++ p);if(p ^ i)for(int j = 0; j <= n; ++ j)std::swap(a[i][j], a[p][j]);for(int j = 0; j < n; ++ j)if(j ^ i){double tmp = a[j][i] / a[i][i];for(int k = 0; k <= n; ++ k)a[j][k] -= a[i][k] * tmp;}}}
}A;
struct ACautomaton
{int cnt;struct node{node *suc[10], *fl;int ed, id;inline node(int _id){for(int i = 0; i < 26; ++ i)suc[i] = NULL;ed = 0;id = _id;}}*rt;inline ACautomaton(){cnt = 0;rt = new node(cnt ++);rt->fl = rt;}inline int insert(char *str, int len, int id){node *u = rt;for(int i = 0; i < len; u = u->suc[str[i] - 'A'], ++ i)if(u->suc[str[i] - 'A'] == NULL)u->suc[str[i] - 'A'] = new node(cnt ++);u->ed = 1;return u->id;}inline void build(){std::deque<node*> que;que.clear();for(int i = 0; i < 26; ++ i)if(rt->suc[i] != NULL)rt->suc[i]->fl = rt, que.push_back(rt->suc[i]), A.a[rt->suc[i]->id][0] = p[i];else if(i < m)A.a[0][0] += p[i];for(; ! que.empty(); que.pop_front()){node *u = que.front();for(int i = 0; i < 26; ++ i)if(u->suc[i] != NULL){if(! u->ed)A.a[u->suc[i]->id][u->id] = p[i];node *p = u->fl;for(; p != rt && p->suc[i] == NULL; p = p->fl);u->suc[i]->fl = p->suc[i] == NULL ? p : p->suc[i];que.push_back(u->suc[i]);}else{u->suc[i] = u->fl->suc[i];if(u->suc[i] != NULL && ! u->ed)A.a[u->suc[i]->id][u->id] = p[i];else if(i < m && ! u->ed)A.a[0][u->id] += p[i];}}A.n = cnt;A.a[0][cnt] -= 1;for(int i = 0; i < cnt; ++ i)A.a[i][i] += -1;}
}ACA;
int main()
{#ifndef ONLINE_JUDGEfreopen("BZOJ1444.in", "r", stdin);freopen("BZOJ1444.out", "w", stdout);#endifscanf("%d%d%d", &n, &l, &m);for(int i = 0; i < m; ++ i){int x, y;scanf("%d%d\n", &x, &y);p[i] = (double)x / y;}static int ed[N];for(int i = 0; i < n; ++ i){static char str[L];scanf("%s", str);ed[i] = ACA.insert(str, l, i);}ACA.build();A.gauss();for(int i = 0; i < n; ++ i)printf("%.2lf\n", A.a[ed[i]][A.n] / A.a[ed[i]][ed[i]] == 0 ? 0 : A.a[ed[i]][A.n] / A.a[ed[i]][ed[i]]);
}