它
【问题描述】
N个人坐成一圈，其中第K个人拿着一个球。每次每个人会以一定的概率向
左边的人和右边的人传球。当所有人都拿到过球之后，最后一个拿到球的人即为
胜者。求第N个人获胜的概率。 （所有人按照编号逆时针坐成一圈）
【输入格式】
第一行一个数T代表数据组数。
对于每组数据，第一行两个整数N,K如题意所述。
接下来每行一个实数p代表该人将球传给右边的人的概率。
【输出格式】
对于每组数据，一行一个实数代表答案，保留9位小数。
【样例输入】
1
5 1
0.10
0.20
0.30
0.40
0.50
【样例输出】
0.007692308
【样例解释】
然后鸟是我的。
【数据规模与约定】
对于20%的数据， N ≤ 3。
70%的数据，T,N ≤ 10。
对于100%的数据，T ≤ 10000,1≤ N ≤ 100。
#include<cstdio>
using namespace std;
const int N=+;
int T,n,k,pre[N],next[N];
long double p[N],q[N];
void deal(int b){
int a=pre[b],c=next[b];
long double pa=p[a],pb=p[b],pc=p[c];
p[a]=pa*pb/(-pa*(-pb));
q[a]=-p[a];
q[c]=(-pc)*(-pb)/(-pb*(-pc));
p[c]=-q[c];
next[a]=c;pre[c]=a;
}
long double solve(){
if(n<=) return ;
if(n<=) return k==?p[]:q[];
for(int i=;i<=n;i++) pre[i]=i-,next[i]=i+;
pre[]=n;next[n]=;// 记录向左向右传递的概率
if(k==){
for(int i=;i<n-;i++) deal(i);
return p[];
}
if(k==n-){
for(int i=;i<n-;i++) deal(i);
return q[n-];
}
for(int i=;i<n-;i++) if(i!=k) deal(i);
deal(k);
return q[k]*p[]+p[k]*q[n-];
}
double v;
#define name "it"
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
scanf("%lf",&v);
p[i]=v;
q[i]=-v;
}
printf("%.9lf\n",(double)solve());
}
return ;
}
/*
p 数组向左传的概率
q 数组向右传的概率
*/
思路：看的别人的代码，没怎么看懂~~-_-