2022 软件学院 AK 杯程序设计竞赛

Problem H. Serein的概率论

在丘丘幼儿园大班的概率论课上,Serein 学到了位运算和概率。他认为自己已经熟练地掌握了这两个知识点,于是他找到了 Ustinian 来出题考考自己。

Ustinian 给了 Serein n 个长度为 m 且只包含 01 的数字串,Ustinian 会对这些数字串操作 q 次。每次 Ustinian 会选择两个数字串 s_is_j,并选择两个位置 l,r,对于所有的 x \in [l,r],将 s_j[x] 替换为 s_j[x] \& s_i[x]s_j[x] 为第 j 个数字串的第 x 位,其中 \& 为位运算中的与运算。但是对于第 i 次操作,只有 p_i/100 的概率成功。

Ustinian 想让 Serein 计算出 q 次操作后,n 个数字串按位与运算后得到的数字串中 1 的个数的期望。Serein 并不能解决这道问题,但是他不想丢面子,于是他想请聪明的你帮他计算出这道题的答案。

输入

第一行两个整数 n,m(2 \leq n \leq 100,1 \leq m \leq 1000),代表数字串的个数和长度。

接下来 n 行每行一个长度为 m 且只包含 01 的数字串。

n + 2 行包含一个整数 q(1 \leq q \leq 2 \times 10^3),代表操作次数。

接下来 q 行,每行五个整数 i,j,l,r,p(1 \leq i,j \leq n,1 \leq l \leq r \leq m,0 \leq p \leq 100),代表操作两个数字 串的编号,操作的位置范围以及成功概率。保证 i \neq j

输出

输出一个数,代表所求期望。如果答案为小数,我们建议你至少保留3位小数。

假设你的答案是p,标准答案是q,我们保证所有满足∣p−q∣\leq 0.01 的答案都会被判定为正确。

样例

标准输入 复制文本
3 3 
100 
110 
111 
1 
1 2 1 2 0
标准输出 复制文本
1

提示

由于 p = 0,p/100 = 0,仅有的一次操作不会成功,所以操作后的数字串始终与原数字串相同。原数字串按位与运算的结果为 100,仅有一个 1,所以答案为1

作为提醒,与运算的运算规则是 0 \& 0 = 0, 0 \& 1 = 0, 1 \& 0 = 0, 1 \& 1 = 1

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 37
通过 9

A B C D E F G H I J

比赛结束时将在信205 B进行滚榜,有兴趣的同学可以留下来看
注意D题中的!是阶乘的意思
题目难度总体递增但不保证单调递增,被前面题卡住的可以往后面看看
本次ak杯 16:30 封榜,17:10 比赛结束
由于刚开始服务器问题,本次ak杯延长10min,到17:10结束
第一题,只需要输出三次I Miss Serein