网站营销学多久,网站访问量来源,手机医疗网站,网站建设费用高传送门
题意#xff1a;开始时你有一个数000,每次选出[0,2n−1][0,2^n-1][0,2n−1]中的一个数进行按位或#xff0c;每个数选中的概率给定。求得到2n−12^n-12n−1的期望操作次数。 1≤n≤201\leq n\leq 201≤n≤20
神仙题
首先发现每一位都是独立的#xff0c;可以分开考…传送门
题意开始时你有一个数000,每次选出[0,2n−1][0,2^n-1][0,2n−1]中的一个数进行按位或每个数选中的概率给定。求得到2n−12^n-12n−1的期望操作次数。
1≤n≤201\leq n\leq 201≤n≤20
神仙题
首先发现每一位都是独立的可以分开考虑。
对于一个集合SSS,记F(S)F(S)F(S)表示SSS的每一个元素出现的期望操作次数组成的可重集记Max(S)max(F(S)),Min(S)min(F(S))Max(S)max(F(S)),Min(S)min(F(S))Max(S)max(F(S)),Min(S)min(F(S))
记S2n−1S2^n-1S2n−1,我们要求的就是E(Max(S))E(Max(S))E(Max(S))
这个不好求但可以Min-Max容斥一下
E(Max(S))∑T⊆S(−1)∣T∣1E(Min(T))E(Max(S))\sum_{T\subseteq S}(-1)^{|T|1}E(Min(T))E(Max(S))T⊆S∑(−1)∣T∣1E(Min(T))
可以直接枚举子集现在考虑怎么求E(Min(T))E(Min(T))E(Min(T))
这玩意的意义是或到和TTT有交集的期望次数
设每次选出一个和TTT有交集的数的概率是ppp
E(Min(T))∑i1∞i(1−p)i−1pE(Min(T))\sum_{i1}^{\infin}i(1-p)^{i-1}pE(Min(T))i1∑∞i(1−p)i−1p
p∑i1∞i(1−p)i−1p\sum_{i1}^{\infin}i(1-p)^{i-1}pi1∑∞i(1−p)i−1
记
s∑i1∞i(1−p)i−1s\sum_{i1}^{\infin}i(1-p)^{i-1}si1∑∞i(1−p)i−1
(1−p)s∑i2∞(i−1)(1−p)i−1(1-p)s\sum_{i2}^{\infin}(i-1)(1-p)^{i-1}(1−p)si2∑∞(i−1)(1−p)i−1
∑i1∞(i−1)(1−p)i−1\sum_{i1}^{\infin}(i-1)(1-p)^{i-1}i1∑∞(i−1)(1−p)i−1
ps∑i1∞(1−p)i−1ps\sum_{i1}^{\infin}(1-p)^{i-1}psi1∑∞(1−p)i−1
∑i0∞(1−p)i\sum_{i0}^{\infin}(1-p)^ii0∑∞(1−p)i
(1−p)ps∑i1∞(1−p)i(1-p)ps\sum_{i1}^{\infin}(1-p)^i(1−p)psi1∑∞(1−p)i
p2s1p^2s1p2s1
s1p2s\frac{1}{p^2}sp21
E(Min(T))ps1pE(Min(T))ps\frac{1}{p}E(Min(T))psp1
ppp仍然不好求。
正难则反我们求和TTT没有交集的概率
即TTT的补集的子集的概率之和
第一次写的子集标记发现会被算多次
然后发现不是个FWTFWTFWT板子吗
然后没了
注意不枚举空集 如果遇到无穷大直接输出
复杂度O(n2n)O(n2^n)O(n2n)
#include iostream
#include cstdio
#include cstring
#include cctype
using namespace std;
double p[120];
const int d[]{0,1,1,2,1,2,2,3};
inline int count(int x)
{int ans0;while (x){ansd[x7];x3;}return ans;
}
int main()
{int n;scanf(%d,n);for (int i0;i(1n);i) scanf(%lf,p[i]);for (int mid1;mid(1n);mid1)for (int s0;s(1n);s(mid1))for (int k0;kmid;k)p[smidk]p[sk];double sum0;for (int i1;i(1n);i){double t1-p[(~i)((1n)-1)];if (t1e-10){puts(INF);return 0;}t1/t;sum((count(i)1)? t:-t);}printf(%.10f\n,sum);return 0;
}wtcl
