题解 P3175 【[HAOI2015]按位或】

发一个不要什么前置技能的解法。 设或结果为$S$的期望步数为$f[S]$，$S$出现的几率为$p[S]$，则 $\displaystyle f[S]=\sum_{k=1}^\infty k(P^k[S]-P^{k-1}[S])$ 可以理解为$k$步得到答案的期望减去$k-1$步及以前得到答案的期望。 设$f$的莫比乌斯变换为$F$,$p$的莫比乌斯变换为$P$，则 $\displaystyle F[S]=\sum_{k=1}^\infty k(P^k[S]-P^{k-1}[S])$ $=\displaystyle-\sum_{k=1}^\infty P^k[S]$ $=\begin{cases}\displaystyle\frac{-1}{1-P[S]}(P[S]!=1)\\=0(P[S]=1)\end{cases}$ 直接套用$FMT$即可。时间复杂度$O(n2^n)$。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) template<typename T>inline void read(T &x) { T f=1;x=0;char c; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c^48); x*=f; } using namespace std; static int n,Len; static double f[1<<20]; inline void init() { read(n);Len=1<<n; Rep(i,0,Len-1)scanf("%lf",&f[i]); } inline void FMT(double *a,double type) { for(register int z=1;z<Len;z<<=1) Rep(j,0,Len)if(z&j)a[j]+=type*a[j^z]; } const double eps=1e-9; inline void solve() { FMT(f,1); Rep(i,0,Len-1)f[i]=fabs(f[i]-1)<eps?0:1.0/(f[i]-1.0); FMT(f,-1); if(f[Len-1]<eps)return (void)puts("INF"); printf("%.8lf\n",f[Len-1]); } int main() { freopen("FMT.in","r",stdin); freopen("FMT.out","w",stdout); init(); solve(); return 0; } ```