题解
按照惯例，我们先进行拆位，每一个二进制位分开考虑，假设第
i
i
i 位第一次变为1的时间是
f
(
i
)
f(i)
f(i)，那么答案就是
E
(
max
?
{
f
(
i
)
}
)
E(\max\{f(i)\})
E(max{f(i)})。
这么
max
?
\max
max 符号在期望的里面，不能直接拿出来，所以最好的处理办法就是对它使用 Min-Max 反演：
E
(
max
?
i
∈
S
{
f
(
i
)
}
)
=
∑
T
≠
?
,
T
?
S
(
?
1
)
∣
T
∣
?
1
E
(
min
?
i
∈
T
{
f
(
i
)
}
)
E(\max_{i\in S}\{f(i)\})=\sum_{T\neq ?,T\subseteq S}(-1)^{|T|-1}E(\min_{i\in T}\{f(i)\})
E(i∈Smax?{f(i)})=T?=?,T?S∑?(?1)∣T∣?1E(i∈Tmin?{f(i)})
反演一下就简单多了，我们只需要求出每个集合内第一次出现1的期望时间即可。设
s
p
S
=
∑
T
?
S
p
T
sp_S=\sum_{T\subseteq S}p_T
spS?=∑T?S?pT?，那么有
E
(
min
?
i
∈
S
{
f
(
i
)
}
)
=
s
p
I
?
S
1
?
s
p
I
?
S
+
1
=
1
1
?
s
p
I
?
S
E(\min_{i\in S}\{f(i)\})=\frac{sp_{I-S}}{1-sp_{I-S}}+1=\frac{1}{1-sp_{I-S}}
E(i∈Smin?{f(i)})=1?spI?S?spI?S??+1=1?spI?S?1?
这个
s
p
sp
sp 用沃尔什变换求一下即可。
代码
今天发现一个巨坑，就是主函数想要用逗号执行一步操作后返回值，如果忘了在后面加,0并且前面部分返回的值正好是int则不会报错，但是运行时会RE。
#include<bits/stdc++.h>
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=1048581;
const ll INF=1e18;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='\n'){
if(x<0)putchar('-'),x=-x;
ptf[lpt=1]=x%10;
while(x>9)x/=10,ptf[++lpt]=x%10;
while(lpt)putchar(ptf[lpt--]^48);
if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}
int n,g[MAXN];
const double eps=1e-9;
double p[MAXN],ans;
signed main()
{
n=read();
for(int s=0;s<(1<<n);s++)scanf("%lf",p+s);
for(int k=0;k<n;k++)
for(int s=0;s<(1<<n);s++)
if((s>>k)&1)p[s]+=p[s^(1<<k)];
g[0]=-1;
for(int s=1;s<(1<<n);s++)g[s]=(s&1)?-g[s>>1]:g[s>>1];
for(int s=1,lim=(1<<n)-1;s<=lim;s++){
if(1-p[lim^s]<eps)return printf("INF\n"),0;
ans+=1.0*g[s]/(1-p[lim^s]);
}
printf("%.10f\n",ans);
return 0;
}
|