传球游戏

Description

小 (mathrm{y}) 痴迷于玩游戏。

班队课上文艺委员小 (mathrm{y}) 组织大家坐成一圈玩传球游戏，每个人都可以把球向左或者向右传。当然每个同学对于自己左右的伙伴喜爱程度可能不一样，所以拿到球之后往两边传的概率也不一样。最后一个被传到球的人被认为是胜利者。作为游戏的组织者，小 (mathrm{y}) 想知道选定自己的某个死党作为游戏的开始者时，自己的胜率是多少。

Input

输入文件solve.in包含多组数据。

第一行包含一个整数，表示数据组数。

每组数据第一行包含两个整数 (N,K) ，表示游戏人数（小 (mathrm{y}) 位置为 (N) ）以及小 (mathrm{y}) 死党的位置。接下来是 (N) 行，每行包含一个实数 (P_i) ，表示第 (i) 个人传球给自己右边概率（小 (mathrm{y}) 组织大家按编号逆时针坐成一圈）。

Output

输出文件为game.out

对于每组数据，输出小 (mathrm{y}) 的胜率，保留 (9) 位小数。

Sample

Sample Input

Sample Output

0.007692308

Limit

(20\%) 的数据满足 (Nle 3) ；

(70\%) 的数据满足 (T,Nle 100) ；

(100\%) 的数据满足 (Tle 10000,1<Nle 100) 。

Solution

~~先摘抄一段题解。~~ 考虑相邻的三个人 (a,b,c) ，假设球一开始在 (a) 手上，在球传到 (a) 的左边之前 (a) 通过 (b) 把球传给 (c) 的概率设为 (x) ；假设球在 (b) ，球传到 (a) 的左边之前传给 (c) 的概率为 (y) ，那么有 $$egin{cases} x=p[a] imes y y=p[b]+(1-p[b]) imes x end{cases}$$ 于是我们可以解出 (x) 。同理可以解出球从 (c) 的手上不经过其他人传到 (a) 的概率。

这样一来我们就可以用这两个概率替换 (a) 往右传的概率和 (c) 往左传的概率，相当于把 (b) 删除。

不断删除点，直至最后剩下 (1,n,n-1,k) ，然后把 (k) 删除，答案就变成了 $$(1-p[K]) imes p[1] + p[K] imes (1-p[n - 1])$$

然后再特判一下 (K=n-1) 或 (K=1) 的情况就好了。

注意此题要使用long double。

#include<bits/stdc++.h>
using namespace std;
#define N 101
#define rep(i, a, b) for (int i = a; i <= b; i++)

int n, K;
long double dp[N][N], p[N], q[N];
double t;
int pre[N], nxt[N];

inline void del(int b) {
	int a = pre[b], c = nxt[b];
	long double pa = p[a], pb = p[b], pc = p[c];
	p[a] = pa * pb / (1 - pa * (1 - pb)), q[a] = 1 - p[a];
	q[c] = (1 - pc) * (1 - pb) / (1 - pb * (1 - pc)), p[c] = 1 - q[c];
	nxt[a] = c, pre[c] = a;
}

inline long double solve() {
	if(n <= 2) return 1;
	if(n == 3)return K == 1 ? p[1] : q[2];
	rep(i, 1, n) pre[i] = i - 1, nxt[i] = i + 1; pre[1] = n, nxt[n] = 1;
	if(K == 1) { rep(i, 2, n - 2) del(i); return p[1]; }
	if(K == n - 1) { rep(i, 2, n - 2) del(i); return q[n - 1]; }
	rep(i, 2, K - 1) del(i);
	rep(i, K + 1, n - 2) del(i);
	del(K);
	return q[K] * p[1] + p[K] * q[n - 1];
}

int main() {
	freopen("game.in", "r", stdin); freopen("game.out", "w", stdout);
	int T; cin >> T;
	while(T--) {
		scanf("%d%d", &n, &K);
		rep(i, 1, n) scanf("%lf", &t), p[i] = t, q[i] = 1 - t;
		printf("%.9lf
", (double)solve());
	}
	return 0;
}