Description:

刚开始你有一个数字 ,每一秒钟你会随机选择一个 的数字,与你手上的数字进行按位或操作,选择数字 的概率是 。保证 ,问期望多少秒后,你手上的数字变成,无解输出



Solution:

如果令 表示在进行完 次操作之后,手上的数为 的概率,令 ,那么显然

$$Ans=\sum_{i=1}^{\infty}(F_i(U)-F_{i-1}(U))*i=F_{\infty}(U)-\sum_{i=0}^{\infty}F_{i}(U)$$

其中$$F_i(x)=\sum_a^x \sum_b^x [a|b=x]F_{i-1}(a)*P(b)$$

,那么

$$G_i(x)=\sum_{a|x=x} \sum_{b|x=x} F_{i-1}(a)*P(b)=\sum_{a|x=x} F_{i-1}(a) * \sum_{b|x=x} P(b)=(\sum_{b|x=x} P(b))^i=G_1(x)^i$$

观察 的定义式 ,令函数 表示 的二进制表示中有多少个 ,根据莫比乌斯反演有:

$$F_i(x)=\sum_{s|x=x}(-1)^{C(x)-C(s)}G_i(s)=\sum_{s|x=x}(-1)^{C(x)-C(s)}G_1(s)^i$$

所以:$$Ans=F_{\infty}(U)-\sum_{i=0}^{\infty}\sum_{s|U=U}(-1)^{C(U)-C(s)}G_1(s)^i=F_{\infty}(U)-\sum_{s|U=U}(-1)^{C(U)-C(s)}\sum_{i=0}^{\infty}G_1(s)^i$$

求和可得:

$$Ans=\sum_{s|x=x}(-1)^{C(U)-C(s)}G_1(U)^{\infty}+\sum_{s|U=U~and~s\neq U}(-1)^{C(U)-C(s)}\frac{1}{G_1(s)-1}-\sum_{i=0}^{\infty}G_1(U)^i$$

$$Ans=\infty+\sum_{s|U=U~and~s\neq U}(-1)^{C(U)-C(s)}\frac{1}{G_1(s)-1}-\infty=\sum_{s|U=U~and~s\neq U}(-1)^{C(U)-C(s)}\frac{1}{G_1(s)-1}$$

怎么判断无解,只用看看最后算出来的Ans是不是收敛的,如果是的,就是有解,否则输出

Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N;
double P[2000010]={0};
int N2;
double S[2000010]={0};
int Num[2000010]={0};

int main()
{
    cin>>N;
    N2=1<<N;
    for(int i=0;i<N2;i++)
    {
        scanf("%lf",&P[i]);
        S[i]=P[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N2;j++)
            if(j&(1<<i))
            {
                S[j]+=S[j^(1<<i)];
                Num[j]++;
            }
    }
    for(int i=0;i<N2-1;i++)
        if(S[i]>=1-1e-8)
        {
            cout<<"INF"<<endl;
            return 0;
        }
    double Ans=0;
    for(int i=0;i<N2-1;i++)
    {
        if((N-Num[i])&1)
            Ans-=1/(S[i]-1);
        else Ans+=1/(S[i]-1);
    }
    printf("%.10lf\n",Ans);
    return 0;
}