记录编号	590941	评测结果	AAAAAAAAAA
题目名称	[HNOI 2015]亚瑟王	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	4.083 s
提交时间	2024-07-13 15:52:00	内存使用	4.18 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
int t;
double f[255][255];
signed main(){
    freopen("arthur.in", "r", stdin);
    freopen("arthur.out", "w", stdout);
    cin >> t;
    while(t --){
        int n = mread(), k = mread();
        int a[n + 5];
        double p[n + 5];
        for(int i = 1; i <= n; i ++){
            cin >> p[i] >> a[i];
        }
        f[1][0] = pow(1.0 - p[1], k);
        f[1][1] = 1 - f[1][0];
        for(int i = 2; i <= n; i ++){
            for(int j = 0; j <= i; j ++){
                f[i][j] = f[i - 1][j] * pow(1.0 - p[i], k - j) + f[i - 1][j - 1] * (1 - pow(1.0 - p[i], k - j + 1));
            }
        }
        double ans = 0, g[n + 5] = {0};
        f[0][0] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = 0; j <= i; j ++){
                g[i] += f[i - 1][j] * (1.0 - pow(1.0 - p[i], k - j));
            }
            ans += g[i] * (double)a[i];
        }
        printf("%.10lf\n", ans);
    }
    return 0;
}