如何修改网站后台的用户名和密码,制作网站软件都在什么公司,网站导航菜单代码,电子商务网站开发基本流程图解析
显然可以利用期望的线性性对每张牌单独计算贡献。 现在的关键就是如何求出每张牌被使用的概率。
考虑第 iii 张牌#xff0c;如果它的前面 [1,i−1][1,i-1][1,i−1] 中有 jjj 张牌被使用#xff0c;那么它被使用的概率就是 1−(1−pi)r−j1-(1-p_i)^{r-j}1−(1−pi)…解析
显然可以利用期望的线性性对每张牌单独计算贡献。 现在的关键就是如何求出每张牌被使用的概率。
考虑第 iii 张牌如果它的前面 [1,i−1][1,i-1][1,i−1] 中有 jjj 张牌被使用那么它被使用的概率就是 1−(1−pi)r−j1-(1-p_i)^{r-j}1−(1−pi)r−j。 根据这个设计 fi,jf_{i,j}fi,j 表示前 iii 张牌中使用了 jjj 张的概率也不难进行转移 fi,jfi−1,j−1(1−(1−pi)r−j1)fi−1,j∗(1−pi)r−jf_{i,j}f_{i-1,j-1}(1-(1-p_i)^{r-j1})f_{i-1,j}*(1-p_i)^{r-j}fi,jfi−1,j−1(1−(1−pi)r−j1)fi−1,j∗(1−pi)r−j 求出 fff 后再用其求出每张牌的概率即可。 预处理 (1−pi)k(1-p_i)^k(1−pi)k时间复杂度 O(Tnr)O(Tnr)O(Tnr)。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(ok\n)
inline ll read(){ll x(0),f(1);char cgetchar(); while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return f*x;
}const int N250;
const int mod1e97;int n,m;
double p[N],f[N][N],mi[N][N];
int d[N];
void work(){nread();mread();for(int i1;in;i) scanf(%lf%d,p[i],d[i]); for(int i1;in;i){mi[i][0]1;for(int j1;jm;j) mi[i][j]mi[i][j-1]*(1-p[i]);}f[0][0]1;for(int i1;in;i){f[i][0]f[i-1][0]*mi[i][m];for(int j1;ji;j){f[i][j]f[i-1][j-1]*(1-mi[i][m-j1])f[i-1][j]*mi[i][m-j];}}double ans(0);for(int i1;in;i){for(int j1;ji;j) ansd[i]*f[i-1][j-1]*(1-mi[i][m-j1]);}printf(%.10lf\n,ans);
}
signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifint Tread();while(T--) work();return 0;
}
/*
*/
