题目描述

题目译自 BalticOI 2022 Day2「Boarding Passes」

在成功遵守当地的风俗之后，你正好赶上了轮船的出发时间。然而，你没有想到会有那么多人前往吕贝克！由于你不想在颁奖仪式上迟到（你还需要一些时间将你所有偷来的艺术品存放在旅店里），你想加快轮船的登船速度。

船上有一排 $N$ 个座位，共 $N$ 名乘客预订了所有座位。每位乘客都有一张船票，上面写着他们的指定座位和 $G$ 个登船组中的一组。

登船时，一次会叫一个组的乘客登船。每个登船组内的乘客将以随机顺序登船，即对于所有可能的登船顺序，出现概率相等。每位乘客可以在第一个座位的前面或最后一个座位的后面登船，然后在另一位乘客登船前移到他们的指定座位。

你确定这个过程中，当一个乘客要经过已经入座的乘客时最耗时（装有所有这些领带的行李在过道上是一个相当大的障碍）。幸运的是，你在附近的储物柜里发现了一件工作人员的制服，所以你可以决定各组乘客的登船顺序，并在登船开始前告诉每位乘客，是要从所有座位的前面还是后面登船。

编写一个程序，利用船票信息计算出在登船过程中，如果你确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

注意

给定一个登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的期望被定义为：

其中 $p_k$ 是登船时一个乘客要经过已经入座的乘客的次数恰好为 $k$ 的概率。换句话说，这是每个登船组中所有可能的乘客登船顺序中一个乘客要经过已经入座的乘客的平均次数。

输入格式

输入包含一个由 $N$ 个字符组成的字符串 $s_1\ldots s_N$，其中 $s_i$ 是前 $G$ 个大写英文字母中的一个，表示坐在第 $i$ 个座位的乘客所属的登船组（最前面的座位为 $1$ 号座位）。

输出格式

输出一个实数，表示确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

如果你的输出与答案的绝对误差不大于 $0.001$，则认为你的输出是正确的。

AACCAA

1

HEHEHEHIHILOL

7.5

ONMLKJIHGFEDCBAABCDEFGHIJKLMNO

0

AAAAAAAAAAAAA...AAAAAAAAAAAAAA

100800.5

数据范围与提示

对于所有数据，满足 $1\le G\le 15,1\le N\le 10^5$。

详细子任务附加限制及分值如下表：