[NOI1999Day1-B]钉子和小球

内存限制：256 MB 时间限制：1000 ms

有一个三角形木板,竖直立放，上面钉着 $n(n+1)/2$ 颗钉子，还有 $(n+1)$ 个格子（当 $n=5$ 时如图 1）。每颗钉子和周围的钉子的距离都等于 $d$，每个格子的宽度也都等于 $d$，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。

让一个直径略小于 $d$ 的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各 $1/2$ ），且球的中心还会正对着下一颗将要碰上的钉子。例如图 2 就是小球一条可能的路径。

我们知道小球落在第 $i$ 个格子中的概率 $p_i=C^i_n/2^n=\frac{n!}{i!(n-i)!}/2^n$，其中 $i$ 为格子的编号，从左至右依次为 $0,1,...,n$。

现在的问题是计算拔掉某些钉子后，小球落在编号为 $m$ 的格子中的概率 $p_m$。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

屏幕快照 2019-06-13 上午10.42.46.png

第 $1$ 行为整数 $n（2 \le n \le 50）$和 $m（0 \le m \le n）$。以下 $n$ 行依次为木板上从上至下 $n$ 行钉子的信息，每行中 ‘*’ 表示钉子还在，‘.’ 表示钉子被拔去，注意在这 $n$ 行中空格符可能出现在任何位置。

仅一行，是一个既约分数 $(0$ 写成 $0/1)$，为小球落在编号为 $m$ 的格子中的概率 $p_m$。既约分数的定义：$A/B$ 是既约分数，当且仅当 $A、B$ 为正整数且 $A$ 和 $B$ 没有大于 $1$ 的公因子。

5 2
*
   * .
  * * *
 * . * *
* * * * *

7/16

C0285 [NOI1999Day1-B]钉子和小球