#PQJ123x560. QOJ 123_560
QOJ 123_560
第二轮第一试 隧道 隧道 【故事背景】 JSOI 是一个有着高度发达交通网络的王国。近日,为了预防敌国间谍的破 坏活动,国王JS 命令交通大臣JYY 检查一处地下通道系统的抗打击能力。 【问题描述】 JSOI 的地下通道系统由𝑅行𝐶列共𝑅×𝐶个关键节点组成。行和列分别用0到 𝑅−1和0到𝐶−1编号,其中最左列(0)和最右列(𝐶−1)的关键节点是通道 系统的地上出入口。通道系统由水平和竖直的单位长度无向隧道相连,构成一个 网格图。下图展示了一个3 行4 列的地下通道系统。
经过情报部门的精密估计,对于每条地下隧道都有一个概率𝑝,表示这条地 下隧道被破坏的概率。每条隧道被破坏均为独立事件。 现在给出了这个地下网络,JYY 需要计算在遭遇敌军破坏后,地下通道系统 仍然能够运作的概率。地下通道系统能运作当且仅当存在一系列未被破坏的隧道, 经由这些隧道能从第0 列的某个地上出入口到达第𝐶−1列的某个地上出入口。 【输入格式】 从文件tunnel.in 中读入数据。 第一行包含两个正整数𝑅、𝐶。 接下来𝑅行,每行包含𝐶−1个正整数。第𝑖行的第𝑗个正整数表示坐标为(𝑖− 1, 𝑗−1)节点的右侧隧道被破坏的概率(百分数)。 接下来𝑅−1行,每行包含𝐶−2个正整数。第𝑖行的第𝑗个正整数表示坐标为 (𝑖−1, 𝑗)节点的下方隧道被破坏的概率(百分数)。 【输出格式】 输出到文件tunnel.out 中。 输出一行一个整数,表示所有关键节点仍然连通的概率。为了避免复杂的浮 点数运算,设最终答案的最简有理数表示为 8 9,你只需要输出𝑝∙𝑞<= mod (10# + 7)的值。𝑞<=是满足𝑞⋅𝑞<= mod 10# + 7 = 1的最小正整数。
第二轮第一试 隧道 【样例输入1】 2 3 50 50 50 50 50 【样例输出1】 500000004 【样例输入2】 6 7 73 18 90 15 56 70 88 37 19 1 65 62 83 77 75 48 48 50 31 76 91 25 34 45 65 9 60 9 38 46 51 74 92 67 74 48 81 60 93 38 97 35 38 95 93 52 6 73 96 18 92 11 79 31 34 56 27 70 5 44 13 【样例输出2】 701609622 【数据规模与约定】 对于30%的数据满足𝑅, 𝐶≤4。 对于50%的数据满足𝑅≤8。 对于100%的数据满足1 ≤𝑅×𝐶< 110, 1 ≤𝑝≤99。