AT_code_festival_final_h 部屋割り

高桥君他们在集训时，有 $N$ 个人，需要住进 $K$ 个房间。 他们准备了写有 $1$ 到 $N$ 的抽签号码，按号码从小到大的顺序，依次决定每个人住哪个房间。 高桥君的团队中，有喜欢安静房间的人和喜欢热闹房间的人两种类型。 喜欢安静房间的人，倾向于选择人数最少的房间。在已有的房间分配中，会选择当前人数最少的房间入住。 喜欢热闹房间的人，倾向于选择人数最多的房间。在已有的房间分配中，会选择当前人数最多的房间入住。 无论是哪种类型的人，如果有多个房间同时满足条件，则会在这些房间中等概率随机选择一个入住。 高桥君想在抽签结束、实际分房前，预测每位参与者将与多少人同住一个房间。 请对于每位参与者，求出其与自己同住一个房间的人数的期望值。注意，人数中包括其本人。

输入通过标准输入给出，格式如下： > $N$ $K$ $S$ - 第 $1$ 行包含两个用空格分隔的整数，表示参加集训的人数 $N\ (1\leq N\leq 200,\!000)$ 和房间数 $K\ (1\leq K\leq 200,\!000)$。 - 第 $2$ 行包含一个长度为 $N$ 的字符串 $S$，表示每个参与者的类型。$S$ 仅由字符 `0` 和 `1` 组成，第 $i$ 个字符 $S_i$ 表示抽签号码为 $i$ 的人的类型。若 $S_i$ 为 `0`，则第 $i$ 个人喜欢安静房间；若为 `1`，则喜欢热闹房间。

对于每位参与者，输出其与自己同住一个房间的人数的期望值。共 $N$ 行，第 $i$ 行输出抽签号码为 $i$ 的人的期望值。 允许的相对误差或绝对误差为 $10^{-6}$。

### 样例解释 1 第 $1,2,3$ 个人会以等概率住进 $1,2,4$ 人房间，因此期望值为 $7/3$。第 $4,5$ 个人会以等概率住进 $2,4$ 人房间，因此期望值为 $3$。第 $6,7$ 个人会住进 $4$ 人房间，因此期望值为 $4$。 由 ChatGPT 4.1 翻译