UOJ Logo

NOI.AC

#80. B 君的第三题

统计

B 君的第三题

【题目描述】

朝闻道,夕死可矣。

B 君非常喜欢他的迷宫,他还想收集更多迷宫。

考虑一个 $n × m$ 的网格,行和列都从 $0$ 开始标号。

设第$ i$ 行第 $j $列的格子是 $(i, j)$。

在 $(i, j)$ 和 $(i, j + 1)$ 的之间,可能有垂直的墙。

在 $(i, j) $和 $(i + 1, j) $的之间,可能有垂直的墙。输入两个二维数组 $v$ 和 $h$。

$v$ 数组的大小是 $n × (m − 1)$,其中 $v_{i,j}$ 为 (i, j) 和 $(i, j + 1)$ 的之间的墙出现的概率。

$h$ 数组的大小是 $(n − 1) × m$,其中 $h_{i,j}$ 为 $(i, j)$ 和 $(i + 1, j)$ 的之间的墙出现的概率。

为了使题目更加简单,出现在$ v $和$ h $中的概率用百分数表示,并且只可能是 $0, 50, 100$ 之一。

一个迷宫的魅力值是他的所有连通块大小的平方和。

问这个迷宫魅力值的期望是多少,因为魅力值可能很大,并且不是整数,只需要输出魅力值模 $1000000007$ 的结果即可。

【输入格式】

第一行包含两个整数 $n, m$。

接下来的 $n$ 行,每行包含$ m − 1$ 个数字,表示数组$ v$。接下来的 $n − 1$ 行,每行包含$ m $个数字,表示数组$ h$。

【输出格式】

输出一行一个整数,表示答案。

【样例输入】

2 2
50
50
50 50

【样例输出】

250000012

【样例解释】

魅力值的期望是 $164 / 16$。

一共有 $16$ 种情况。

如果没有墙,或者只有一个墙,魅力值是 $16$。

如果有两个墙,如果他们构成直角,魅力值是 $10$。

如果有两个墙,如果他们构成直线,魅力值是 $8$。如果有三个墙,答案是 $8$。

如果有四个墙,答案是 $4$。

【样例输入】

2 2
100
50
0 50

【样例输出】

10

【样例解释】

魅力值的期望是 $40 / 4$。

一共有四种情况,魅力值为 $16 + 10 + 8 + 6 = 40$。

【数据规模与约定】

对于 $100%$ 的数据,满足 $1 \leq n, m \leq 7$,$v_{i,j}$ 和 $h_{i,j}$ 是 $0, 50, 100$ 之一。

对于 $30%$ 的数据,满足 $v_{i,j}$ 和 $v_{i,j}$ 是 $0, 100$ 之一。

对于 $50%$ 的数据,满足 $v_{i,j}$ 和 $h_{i,j}$ 中,为 $50$ 的不超过 $16$ 个。

对于另 $30%$ 的数据,满足 $1 \leq m \leq 3$。