D - 扑克牌

得分：$400$ 分

问题描述

我们有 $9K$ 张卡牌。对于每个 $i = 1, 2, \dots, 9$，有 $K$ 张卡牌上写着 $i$。
我们随机洗牌并向高滨和青木分发了五张牌 - 四张正面朝上，一张正面朝下。
给定一个表示分发给高滨的牌的字符串 $S$，一个表示分发给青木的牌的字符串 $T$。
$S$ 和 $T$ 是每个由五个字符组成的字符串。每个字符串的前四个字符是 1，2，$\dots$，或者 9，代表正面朝上的牌上的数字。每个字符串的最后一个字符是 #，表示这张牌是正面朝下的。
我们定义五张卡牌的得分为 $\displaystyle \sum_{i=1}^9 i \times 10^{c_i}$，其中 $c_i$ 是数字为 $i$ 的卡牌的数量。
当高滨的手牌得分高于青木的手牌得分时，高滨获胜。
求高滨获胜的概率。

约束

• $2 ≤ K ≤ 10^5$
• $|S| = |T| = 5$
• $S$ 和 $T$ 的前四个字符是 1，2，$\dots$，或者 9。
• $S$ 和 $T$ 中的数字 1，2，$\dots$，9 总共出现最多 $K$ 次。
• $S$ 和 $T$ 的最后一个字符是 #。

输入

从标准输入中给出以下格式的输入：

$K$

$S$

$T$

输出

输出高滨获胜的概率，保留小数位。 你的答案将被判断为正确，当其与我们的答案具有绝对误差或相对误差不超过 $10^{-5}$。

2
1144#
2233#

0.4444444444444444

例如，如果高滨的手牌是 11449，青木的手牌是 22338，则高滨的得分是 $100+2+3+400+5+6+7+8+90=621$，青木的得分是 $1+200+300+4+5+6+7+80+9=612$，结果是高滨获胜。
高滨获胜的条件是高滨的背面朝下的牌的数字大于青木的背面朝下的牌的数字，因此高滨以 $\frac49$ 的概率获胜。

2
9988#
1122#

1.0

6
1122#
2228#

0.001932367149758454

高滨只有当高滨的手牌是 11222，青木的手牌是 22281 时才能获胜，概率为 $\frac2{1035}$。

100000
3226#
3597#

0.6296297942426154