问题 1064 --#2004. 「SDOI2017」硬币游戏

1064: #2004. 「SDOI2017」硬币游戏

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

周末同学们非常无聊,有人提议,咱们扔硬币玩吧,谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色,但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性,所以要找一个同学扔很多很多次硬币,其他同学记录下正反面情况。

H 表示正面朝上, 用 T 表示反面朝上,扔很多次硬币后,会得到一个硬币序列。比如 HTT 表示第一次正面朝上,后两次反面朝上。

但扔到什么时候停止呢?大家提议,选出 n n n 个同学, 每个同学猜一个长度为 m m m 的序列,当某一个同学猜的序列在硬币序列中出现时,就不再扔硬币了,并且这个同学胜利。为了保证只有一个同学胜利,同学们猜的 n n n 个序列两两不同。

很快,n n n个同学猜好序列,然后进入了紧张而又刺激的扔硬币环节。你想知道,如果硬币正反面朝上的概率相同,每个同学胜利的概率是多少。

输入格式

第一行两个数 n n nm m m
接下来 n n n 行,每行一个长度为 m m m 的字符串,表示第 i i i 个同学猜的序列。

输出格式

输出 n n n 行,第 i i i 行表示第 i i i 个同学胜利的概率。选手输出与标准输出的绝对误差不超过 10−6 10 ^ {-6} 106 即为正确。

样例

样例输入

3 3
THT
TTH
HTT

样例输出

0.3333333333
0.2500000000
0.4166666667

数据范围与提示

对于 10% 10\% 10% 的数据,1≤n,m≤3 1 \leq n, m \leq 3 1n,m3
对于 40% 40\% 40% 的数据,1≤n,m≤18 1 \leq n, m \leq 18 1n,m18
对于另外 20% 20\%20% 的数据,n=2 n = 2 n=2
对于 100% 100\% 100% 的数据,1≤n,m≤300 1 \leq n, m \leq 300 1n,m300

输入

输出

提示

来源

 

[提交][状态]