求条玄关

#include<bits/stdc++.h>
using namespace std;
const int N=225;
double v[N],r[N];
double dp[N][N],dp2[N][N];
int n,m;
double ksm(double x,int y){
	double re=1;
	while (y){
		if (y%2)	re*=x;
		x*=x;
		y>>=1;
	}
	return re;
}
double f[N];
double ans;
int main(){
	int t;
	cin>>t;
	while (t--){
		ans=0;
		cin>>n>>m;
		for (int i=1;i<=n;i++)	cin>>v[i]>>r[i],r[i]*=1.0;
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		dp[1][0]=ksm(1.0-v[1],m),dp[1][1]=f[1]=1.0-dp[1][0];
		for (int i=2;i<=n;i++)
			for (int j=0;j<=min(i,m);j++){
				if (i!=j)	dp[i][j]=dp[i-1][j]*ksm(1.0-v[i],m-j);
				if (j)	dp[i][j]+=(dp[i-1][j-1])*(1.0-ksm(1.0-v[i],m-j+1));
				if (j!=i)	f[i]+=dp[i-1][j]*(1.0-ksm(1.0-v[i],m-j));
			}
		for (int i=1;i<=n;i++)	ans+=f[i]*r[i];
		printf("%.10lf",ans);
	}
}