做视频网站需要流媒体吗,那里做一元云购网站,免费建立网站,手机商城设计正题
题目链接:https://www.luogu.com.cn/problem/P3175 题目大意
开始有一个nnn位二进制数s0s0s0#xff0c;每次有pip_ipi概率选取数字iii让sss或上这个数字iii#xff0c;求期望多少次能够让sss的nnn个位都变为111。 解题思路
因为是或所以我们只关心最后一个选中的数…正题
题目链接:https://www.luogu.com.cn/problem/P3175 题目大意
开始有一个nnn位二进制数s0s0s0每次有pip_ipi概率选取数字iii让sss或上这个数字iii求期望多少次能够让sss的nnn个位都变为111。 解题思路
因为是或所以我们只关心最后一个选中的数设第iii位选中的期望次数为E(i)E(i)E(i)的话答案就是max{E(i)}max\{E(i)\}max{E(i)}。
又是期望又是maxmaxmax所以可以直接上min-max\text{min-max}min-max容斥答案就是 ∑T∈Smin{E(i)}(i∈T)∗(−1)∣T∣1\sum_{T\in S}min\{E(i)\}(i\in T)*(-1)^{|T|1}T∈S∑min{E(i)}(i∈T)∗(−1)∣T∣1
算这个东西的话也就是如果我们选中一个与TTT有交集的数就可以退出了。期望次数1/期望概率。所以我们直接算期望概率
也就是我们要算所有∑G∩T≠∅pG\sum_{G\cap T\neq \varnothing}p_{G}∑G∩T∅pG。GGG和TTT的交集非空就去掉所有交集为空的交集为空的就是TTT的补集的子集和。
子集和的话就是直接拿ppp出来跑一次ororor的FWT\text{FWT}FWT的结果就是子集和了。
时间复杂度O(n2n)O(n2^n)O(n2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N121;
const double eps1e-8;
int n;double cnt[N],p[N],ans;
void FWT_or(double *f,int op){for(int p2;pn;p1)for(int k0,lenp1;kn;kp)for(int ik;iklen;i)f[ilen]f[i]*op;return;
}
int main()
{scanf(%d,n);cnt[0]-1;n1n;for(int i0;in;i)scanf(%lf,p[i]);FWT_or(p,1);for(int i0;in;i){if(i)cnt[i]-cnt[i-(i-i)];double e1-p[(n-1)^i];if(fabs(e)eps)continue;anscnt[i]*(1.0/e);}if(anseps)printf(INF);else printf(%.10lf,ans);
}
