#LUOGUP1005. [JLOI2013] 卡牌游戏

    ID: 1379 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划,dp递推2013各省省选吉林

[JLOI2013] 卡牌游戏

题目描述

NN 个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从 11NN 编号。首先第一回合是玩家 11 作为庄家。每个回合庄家都会随机(即按相等的概率)从卡牌堆里选择一张卡片,假设卡片上的数字为 XX,则庄家首先把卡片上的数字向所有玩家展示,然后按顺时针从庄家位置数第 XX 个人将被处决(即退出游戏)。然后卡片将会被放回卡牌堆里并重新洗牌。被处决的人按顺时针的下一个人将会作为下一轮的庄家。那么经过 N1N-1 轮后最后只会剩下一个人,即为本次游戏的胜者。现在你预先知道了总共有 MM 张卡片,也知道每张卡片上的数字。现在你需要确定每个玩家胜出的概率。

这里有一个简单的例子:

例如一共有 44 个玩家,有四张卡片分别写着3,4,5,6.

第一回合,庄家是玩家 11 ,假设他选择了一张写着数字 55 的卡片。那么按顺时针数 1,2,3,4,1,最后玩家 11 被踢出游戏。

第二回合,庄家就是玩家 11 的下一个人,即玩家 22.假设玩家 22 这次选择了一张数字 66,那么 2,3,4,2,3,4,玩家 44 被踢出游戏。

第三回合,玩家 22 再一次成为庄家。如果这一次玩家 22 再次选了 66,则玩家 33 被踢出游戏,最后的胜者就是玩家 22

输入格式

第一行包括两个整数 N,MN,M 分别表示玩家个数和卡牌总数。

接下来一行包含 MM 个整数,分别给出每张卡片上写的数字。

输出格式

输出一行包含 NN 个百分比形式给出的实数,四舍五入到两位小数。分别给出从玩家 11 到玩家 NN 的胜出概率,每个概率之间用空格隔开,最后不要有空格。

5 5
2 3 5 7 11

22.72% 17.12% 15.36% 25.44% 19.36%

4 4
3 4 5 6
25.00% 25.00% 25.00% 25.00%

提示

对于 30%30\% 的数据,有 1N101\le N\le 10

对于 50%50\% 的数据,有 1N301\le N\le 30

对于 100%100\% 的数据,有 1N501\le N\le 50, 1M501\le M\le 50, 11\le 每张卡片上的数字 50\le 50