#P1444. [Jsoi2009]有趣的游戏

    ID: 455 传统题 1000ms 512MiB 尝试: 2195 已通过: 541 难度: 7 上传者: 标签>CF2300提高+/省选-AC 自动机吸收链期望方程期望线性性Gauss–Jordan 消元主元选择

[Jsoi2009]有趣的游戏

题目描述

有 nn 个由前 mm 个大写字母组成的长度为 ll 的串 s1⋯ns_{1\cdots n}。

初始有一个空串 TT,每秒会随机在 TT 的末尾加入一个大写字母,对于第 jj 个大写字母,每秒被加入的概率是 pjqj\frac{p_j}{q_j},并且有 ∑i=1mpiqi=1\sum_{i=1}^m \frac{p_i}{q_i}=1。

问每个串 sis_i 先于其它所有串在 TT 里出现的概率。

输入格式

第一行三个整数 n,l,mn,l,m。

接下来 mm 行,每行两个整数 p,qp,q,第 ii 行的输入表示随机到第 ii 个字母的概率是 pq\frac{p}{q}。

接下来 nn 行,每行一个长度为 ll 的字符串 sis_i。

输出格式

包括 nn 行,第 ii 行一个实数表示串 sis_i 先于其它所有串在 TT 里出现的概率,四舍五入保留两位小数。

3 2 2
1 2
1 2
AB
BA
AA
0.25
0.50
0.25
3 4 2
1 2
1 2
AABA
ABAA
BAAA
0.31
0.33
0.37

数据规模与约定

对于 100%100\% 的数据,1≤n,m,l≤101\leq n,m,l\leq 10,0≤p≤q≤100\leq p\leq q\leq 10 且 gcd⁡(p,q)=1\gcd(p,q)=1。