「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$的概率。
那么答案即为：

$$[x^{2^n-1}](\sum_{k}k\times (p^k-p^{k-1}))$$

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

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

注意对于全集的处理。

---

代码

#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;
}