「HAOI2015」按位或 - 快速莫比乌斯反演(FMT) | Bill Yang's Blog
0%

「HAOI2015」按位或 - 快速莫比乌斯反演(FMT)

题目大意

    刚开始你有一个数字$0$,每一秒钟你会随机选择一个$[0,2^n-1]$的数字,与你手上的数字进行或(c++,c的|,pascal的or)操作。选择数字$i$的概率是$p[i]$。保证$0\le p[i]\le1,\sum p[i]=1$,问期望多少秒后,你手上的数字变成$2^n-1$。


题目分析

快速莫比乌斯变换

记号:$[x^c]A(x)$表示多项式$A$的第$c$项。

将读入的$p$数组看做多项式$p(x)$,用或卷积的乘法考虑:$[x^i]p^k$就表示$k$轮后得到$i$的概率。
那么答案即为:

因为是卷积的快速幂,莫比乌斯变换一下变成点积快速幂。

而$\sum\limits_{k}k \times (p^k-p^{k-1})=-(1+p+p^2+p^3+\cdots)$,这是一个等比数列求和,为$-\frac 1{(1-p)}$。
然后再逆变换一下即可。

注意对于全集的处理。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=1<<20;

struct FastMobiusTransform {
int n,m;
void init(int n) {
this->n=n;
m=1<<n;
}
void transform(double *a,int mul) {
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(j&(1<<i))a[j]+=a[j^(1<<i)]*mul;
}
void fmt(double *a) {transform(a,1);}
void ufmt(double *a) {transform(a,-1);}
} mtf;

int n,tag=0;
double p[maxn];

int main() {
n=Get_Int();
mtf.init(n);
for(int i=0; i<(1<<n); i++) {
scanf("%lf",&p[i]);
if(p[i])tag|=i;
}
if(tag!=(1<<n)-1) {puts("INF");return 0;}
mtf.fmt(p);
for(int i=0; i<(1<<n)-1; i++)p[i]=-1/(1-p[i]);p[(1<<n)-1]=0;
mtf.ufmt(p);
printf("%.10lf\n",p[(1<<n)-1]);
return 0;
}
姥爷们赏瓶冰阔落吧~