#P4224. Togle

    ID: 3442 传统题 1000ms 128MiB 尝试: 7 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-期望方程期望线性性首次步分析对称性分析Gauss–Jordan 消元

Togle

题目描述

给你一个长度为 nn 的 0101 串,以及一个指针,初始时指针在第 i0i_0 个字符上。每回合随机一个 00 到 n−1n-1 中的数 jj,如果指针之前在 ii 上,就花费 ∣i−j∣|i-j| 的时间把指针从 ii 移动到 jj 上,并且把 0101 串的第 jj 位取反。不停这样随机,直到 0101 串变成全 00 或者全 11 为止,问到终止前期望花费的时间是多少?

输入格式

本题有多组数据。

第一行两个整数 n,tn,t,表示串长和数据组数,每组数据的串长是相等的。

接下来 tt 行,每行一个 0101 串和一个整数 s,i0s,i_0,表示初始时的串和初始位置,ss 的长度为 nn。

输出格式

tt 行,每行一个实数表示答案。你的答案被认为是正确的当且仅当,你与标准答案的相对误差小于 10−710^{-7}。

样例

4 4
1000 0
0010 1
0011 2
1010 3
8.9375
8.5625
9.75
10.25

数据规模与约定

对于 100%100\% 的数据:n≤30n\le 30,t≤105t\le 10^5,0≤i0<n0\le i_0<n。