0%

[WF2014H]Pachinko

题目描述

你已被 \(\text{Addictive Coin Machines}\) 聘用去帮助设计风靡全球赌场弹球盘系列的下一款夺人眼球,一本万利,让玩家不能自拔的热门产品。

玩弹球盘需要将球发射到存在着钉子,障碍和靶子的网格中。球会在网格间反弹,直到击中任意一个靶子。玩家会根据击中的靶子获得相应的得分。 下一款弹球盘的网格布局已经设计好了,但是靶子的分值尚未分配。这些分值必须被精心设置,以便像所有赌场设备一样,该游戏是有利可图的,又不至于过于有利可图。因此,弄清楚一个球击中任意特定靶子的概率非常重要。这就是你的工作!

为简单起见,网格被当作一个高矩形,其中有开放的格间(每个用 \(.\) 表示),不能穿过的障碍(每个用 \(‘“\text{X}"’\) 表示)以及靶子 (每个用 \(“\text{T}"\) 表示)。

球会被均匀随机地发射到网格第一层开放的格间中。从那时起,与钉子的碰撞会使以给定概率向上,向下,向左或向右反弹。为简单起见,假定网格中每个格间的这些概率都是对应相等的。如果球反弹到障碍物或试图弹出网格,则球实际上只会停留在原地再次与钉子碰撞。当球击中靶子时,游戏则会立即结束。

你可以放心假定,在击中靶子以前,球到达的平均格间数量不会超过 \(10^9\)。如果球一直在弹来弹去,这就不是一款好玩的游戏了。

对于每一个靶子,计算它被发射的球击中的概率。

输入格式

输入只包含一组测试用例。第一行包含整数 \(w\)\(h\),分别是弹球盘网格的宽和高(\(1\le w\le 20\)\(2\le h \le 10\ 000\))。下一行包含和为 \(100\) 的四个非负整数 \(u,d,l\)\(r\),分别为在任意一个开放格间中,向上、向下、向左或向右反弹的百分比概率。

接下来 \(h\) 行每一行包含 \(w\) 个字符,每个字符是 \(“."\)\(“\text{X}"\),和 \(“\text{T}"\) 三者之一。这些行描述了弹球盘的网格布局。第一行描述了网格第一层的情况,包含了至少一个 \(.\) 且不含 \(“\text{T}"\)

输出格式

对于每一个网格中的 \(“\text{T}"\) 按照从上到下,若在同一行则按从左到右的顺序输出被球击中的概率。输出答案与标准答案的绝对误差最多为 \(10^{-6}\)

题解

首先直接 dp 是不行的,因为题干中没有拓扑序进行后效性的转移。我们不妨设第一列有 \(c\) 个开放格间,我们不妨考虑将题目转化为第一行的开放格间每个有 \(\dfrac{1}{c}\) 的贡献,其余开放格间有 \(0\) 的贡献,求靶子被击中时球获得贡献的期望,因为原题虽然让求出概率,但这样会有诸多限制,并且在非靶子节点的概率会定义不清,所以改为直接求期望更合适。

这样就变成了图的随机游走模型,我们设整体矩形区域为对角线端点为 \((0,0)\)\((h-1,w-1)\) 的矩形区域 \(A\)\(f_{(i,j)}\) 表示到达 \((i,j)\) 这个格间的期望,\((i,j)\) 上的字符为 \(s_{(i,j)}\),向上,向下,向左,向右的位移向量依次是 \(v_0\)\(v_3\)。通过分类讨论,很容易列出方程:

首先,当 \(s_{(i,j)}=“\text{X}"\) 时,\((i,j)\) 无法到达,\(f_{(i,j)}\) 无定义。

之后有,

\[ f_{(i,j)}\ = \sum_{k=0}^{3}\ \begin{cases} p_{v_{k\oplus 1}}f_{(i,j)+v_k}&(i,j)+v_k\notin A\land s_{(i,j)+v_k=“."}\\\\ p_{v_k}f_{(i,j)}&((i,j)+v_k\notin A\lor s_{(i,j)+v_k}=“\text{X}")\land s_{(i,j)=“."}\\\\ 0&\text{otherwise} \end{cases} \]

之后就会有 \(wh\) 个线性方程组,直接用高斯消元求解则为 \(O((wh)^3)\)。考虑优化,我们不难发现这个矩阵十分稀疏,更具体的,若设 \(f_{(i,j)}\) 对应未知数 \(x_{wi+j}\) 那么对于第 \(x_{wi+j}\) 个方程,它包含的未知数的下标范围即为 \([w(i-1)+j,w(i+1)+j]\),最终高斯消元矩阵的有效部分形态如图所示。

我们会发现每次我们对第 \(i\) 行只需要进行一个大小为 \(w\times w\) 的有效矩阵的消元即可,单次复杂度为 \(O(w^2)\),总复杂度为 \(O(hw^3)\)

然而有一种情况需要特殊考虑,即处理第 \(i\) 行时,矩阵 \((i,i)\) 的值已经为 \(0\) 了,如果按照常规的高斯消元,现在需要做的是交换行,在这里也是同理,如图:

这是已经遇到 \(2\) 次该情况,而现在处理黄色行 \(i\) 时又遇到了 \((i,i)\)\(0\) 的情况,这是我们遍历 \([i-w,i+w]\) 的每一行,若发现一个灰色行,即已经在之前已经被处理过的直接跳过,若遇到一个红色行 \(p\),满足 \((p,i)\) 不为 \(0\),则把 \(p\) 行当作当前处理的行,这时要用 \(p\) 行的 \([i,p+w]\)\([p+1,i+w]\) 行进行消元。若不存在符合条件的 \(p\),则说明从题干的角度看 \((\lfloor\dfrac{i}{w}\rfloor,i\mod w)\) 不可达,或者无法到达靶子格间,从矩阵的角度看这一行无解或者有无穷多的解。

但实际上还有一种特殊情况未考虑,即考虑如下数据:

1
2
3
4
5
6
2 4
20 40 0 40
.X
..
.X
.T

对于位于 \((1,1)\) 的点来说,只要进入这个点就再也走不出去了,期望在这里没有定义,但是这与通过一开始分类讨论得到方程 \(0=\frac{2}{5}f_{(1,0)}\) 这是矛盾的,所以我们要对这样的方程进行调整,通过连通性特判这种情况,或者是令方程中由于移向做差让系数变为 \(0\)\(f_{(1,1)}\) 的系数调整一个很小的实数,由于该点出不去,所以也无法对其他点造成影响,也恰好印证了题干中的假设,经过的房间平均个数不超过 \(10^9\)