题解 P3175 [HAOI2015]按位或

1 minute read

Published:

前置知识：FMT (快速莫比乌斯变换)

由于本题题解中的写法基本都是 min-max 容斥，单纯使用 FMT 的题解给的解释又过于简略，所以决定给该写法一个较为详细的解释

先简单介绍一下FMT/FWT：

FMT 叫快速莫比乌斯变换，用于处理 or 卷积，其本质为高维前缀和，同时由于 and 卷积本质上与 or 基本无差（and 卷积本质为高维后缀和），所以也可以用来处理 and 卷积

而 FWT 是快速沃尔什变换，用于处理 xor 卷积，异或本质上就是二进制不进位加法，二维的 FWT 就相当于以 $2$ 的单位根进行 FFT/NTT

设 $f(x)$ 为概率 $P_x$ 的集合幂级数，定义其乘法为或卷积，记 $T$ 为全集。当或操作的次数为 $k$ 时的概率：$[x^T]f^k(x)-f^{k-1}(x)$ ，那么答案就是

\[\displaystyle [x^T] \sum_{k=0}^{\infty} k(f^k(x)-f^{k-1}(x))=-[x^T]\sum_{k=0}^{\infty} f^k(x)\]

现在我们需要做的就是求这个式子，但由于它是无穷级数，且乘法的定义为或卷积，没有什么好的性质。

给出一条结论：对于一个形式幂级数（多项式） $T(x)$ ，记 $f(x)$ 为一个集合幂级数，记 $\hat g(x)$ 为集合幂级数 $g(x)$ 的莫比乌斯变换，那么 $\hat T(f(x))=T(\hat f(x))$ 。

这里的 $\hat T(f(x))$ 定义的不是很严谨，这里并不是表示 $T(x)$ 的莫比乌斯变换（对于形式幂级数做莫比乌斯变换可能没有实际意义），而是表示 $T(f(x))$ 构成的集合幂级数的莫比乌斯变换 。

$f(x)$ 的乘法定义为或卷积，$T(\hat f(x))$ 中 $\hat f(x)$ 的乘法定义为对应位点乘。

这个结论其实也挺好证的。由于对于集合幂级数的运算 $f(x)+g(x)$ 以及 $f(x)g(x)$ 都可以通过先莫比乌斯变换再做 $\hat f(x)+ \hat g(x) $ 以及 $\hat f(x)\hat g(x)$ ，然后再莫比乌斯反演回来来得到。

而莫比乌斯变换后的加法和乘法的定义都和我们正常的形式幂级数的加法和乘法定义相同，所以可以直接拿莫比乌斯变换后的值来代入形式幂级数中，再莫比乌斯反演得到待求值。

对于原题，我们设 $\displaystyle T(f(x))=-\sum_{k=0}^{\infty} f^k(x)$

对于这个东西，我们只需要把 $T(\hat f(x))$ 的每一项都求出来，然后做莫比乌斯变换变回来即可。由于莫比乌斯变换之后的乘法定义为点乘，所以有

\[\displaystyle T(\hat f_S)=-\sum_{k=0}^{\infty} \hat f^k_S=-\frac{1}{1-\hat f_S} ,(\hat f_S\neq 1)\] \[T(\hat f_S)=0,(\hat f_S=1)\]

（原式不收敛，所以等式成立）

最后再做一遍莫比乌斯反演即可。时间复杂度 $O(n2^n)$ 。

#include<bits/stdc++.h>
#define re register int
#define ll long long
#define dl double
#define LL inline ll
#define V inline void
#define I inline int
#define FOR(i,a,b) for(re i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re i=(a),i##i=(b);i>=i##i;--i)
#define gc getchar()
//#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
using namespace std;
char *fs,*ft,buf[1<<18];
const int N=2e6+10,mo=998244353;
const dl eps=1e-8;
LL read(){
	ll p=0; bool w=0; char ch=gc;
	while(!isdigit(ch)) w=ch=='-',ch=gc;
	while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
	return w?-p:p;
}
int n,tot;
LL Pow(ll x,ll y){ ll as=1; for(;y;y>>=1,x=x*x%mo) if(y&1) as=as*x%mo; return as;}
LL ck(ll x){ return x-=mo,x+=x>>63&mo;}
dl f[N];
V FMT(dl *a,int lm,dl tp){
	for(re i=1;i<lm;i<<=1)
		for(re j=0;j<lm;j+=(i<<1))
			for(re k=j;k<j+i;++k)
				a[k+i]+=a[k]*tp;
	return ;
}
V sol(){
	FMT(f,tot+1,1.0);
	FOR(i,0,tot) f[i]=fabs(f[i]-1)<eps?0:1.0/(f[i]-1.0);
	FMT(f,tot+1,-1.0);
	if(f[tot]<=eps) printf("INF");
	else printf("%.8lf",f[tot]);
	return ;
}
int main(){
	n=read(),tot=(1<<n)-1;
	FOR(i,0,tot) scanf("%lf",&f[i]);
	sol();
	return 0;
}

You May Also Enjoy