bzoj4036:[HAOI2015]按位或(FMT)

Author Avatar
Sakits 10月 03, 2018

题解

  集合并卷积形式可以用莫比乌斯变换/反演加速运算(其实FWT也可以)。
  设 fi,Sf_{i,S}ii 秒后手上数字为 SS 的概率,则有:

fi,S=aSbS[ab=S]fi1,apbf_{i, S}=\sum_{a\subseteq S}\sum_{b\subseteq S}[a \cup b = S] f_{i-1,a} * p_b

  设 FFff 的莫比乌斯变换,PPpp 的莫比乌斯变换,则有:

Fi,S=aSbS[abS]fi1,apb=(aSfi1,a)(bSpb)=Fi1,SPS=PSi\begin{aligned} F_{i, S}&=\sum_{a\subseteq S}\sum_{b\subseteq S}[a \cup b \subseteq S] f_{i-1,a} * p_b\\ &=(\sum_{a\subseteq S}f_{i-1,a})*(\sum_{b\subseteq S}p_b)\\ &=F_{i-1, S}*P_S\\ &=P_S^i \end{aligned}

  答案的莫比乌斯变换为:

ansS=i=1i(Fi,SFi1,S)=i=1i(PSiPSi1)={(PS0+PS1+PS2+...+PS)PS<10PS=1={1PS1PS<10PS=1\begin{aligned} ans_S&=\sum_{i=1}^{\infty} i (F_{i, S}-F_{i-1, S})\\ &=\sum_{i=1}^{\infty} i (P_S^i-P_S^{i-1})\\ &= \begin{cases} -(P_S^0+P_S^1+P_S^2+...+P_S^{\infty}) & P_S<1 \\ 0 & P_S=1 \end{cases}\\ &= \begin{cases} \frac{1}{P_S-1} & P_S<1 \\ 0 & P_S=1 \end{cases} \end{aligned}

  再莫反回去即可。注意答案不收敛则无解。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int inf=1e9;
const double eps=1e-9;
int n;
double p[1<<20];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void FMT(double *f, int o)
{
	for(int i=1;i<(1<<n);i<<=1)
	{
		for(int j=0;j<(1<<n);j++)
		if(j&i) f[j]+=f[j^i]*o;
	}
}

int main()
{
	read(n);
	for(int i=0;i<(1<<n);i++) scanf("%lf", &p[i]);
	FMT(p, 1);
	for(int i=0;i<(1<<n);i++)
	if(fabs(p[i]-1)<eps) p[i]=0;
	else p[i]=1/(p[i]-1);
	FMT(p, -1);
	if(p[(1<<n)-1]<eps) puts("INF");
	else printf("%.9lf\n", p[(1<<n)-1]);
}