D-小紫的优势博弈_牛客周赛 Round 85

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 定义一个字符串是“双生串”，当且仅当字符串中每一种字符出现的次数都是偶数次。

$\hspace{15pt}$ 现在，小紫拿到了一个长度为 $n$ ，仅由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串 $s$ ，她准备和小红玩一个游戏：
$\hspace{23pt}\bullet\,$ 小红先手操作，删除该串的一个非空前缀；
$\hspace{23pt}\bullet\,$ 小紫紧接着操作，删除该串的一个后缀（可以是空串）。
$\hspace{15pt}$ 如果最终可以生成一个非空双生串，那么小紫将获得最终的胜利。

$\hspace{15pt}$ 小紫发现这个游戏自己非常劣势，因为小红可以删除到只剩下一个字符导致自己必输，于是她强制让小红随机删除一个前缀（即删除 $1 \sim n$ 个字符）。请你计算小紫最终获胜的概率。

输入描述:

第一行输入一个正整数  代表字符串的长度。 
第二行输入一个长度为 ，由字符  和  组成的字符串 ，代表初始字符串。

输出描述:

在一行上输出一个实数，代表最终小紫获胜的概率。

由于实数的计算存在误差，当误差的量级不超过  时，您的答案都将被接受。具体来说，设您的答案为  ，标准答案为  ，当且仅当  时，您的答案将被接受。

示例1

输入

复制

5
10010

输出

复制

0.2

说明

在这个样例中，小红一共有五种删除前缀的方式：
删除前一个字符，得到 ；此时，小紫只需要删除最后的两个字符，得到 ，此时字符串是双生串，小紫可以获胜；
删除前两个字符，得到 ；
删除前三个字符，得到 ；
删除前四个字符，得到 ；
删除前五个字符，得到 ；
其中，对于后四种情况，小紫无论怎么删除后缀，都无法得到双生串，所以，小紫获胜的概率为 。