menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[FMT]BZOJ4036(HAOI2015)【按位或】题解
local_offer 查看标签
comment 0 条评论

题目概述

刚开始 $x$ 为 $0$ ,每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数,生成 $i$ 的概率为 $p_i$ ,问 $x$ 变成 $2^n-1$ 的期望时间。

解题报告

VFK的FMT论文题,先来讲下(抄下论文)FMT:

全集 $U=\{1,2,\cdots,n\}$ ,令 $2^U$ 表示 $U$ 的子集。定义集合幂级数 $f$ 是定义域在 $x\subseteq2^U$ ( $x$ 是集合)上的函数,$f=\sum_{s\subseteq2^U}f_sx^s$ ,其中 $x^s$ 只是一个符号,表示 $s$ 这个项,$f_s$ 是 $s$ 这个项的系数。

定义集合幂级数的加法运算是每项系数加起来,定义集合幂级数的乘法运算:

$$ f*g=\sum_{s\subseteq2^U}f_sx^s*\sum_{s\subseteq2^U}g_sx^s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ax^Ag_Bx^B=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ag_Bx^{A*B} $$

其中这个 $*$ 是个运算,想要满足上述式子这个 $*$ 就必须满足交换律,结合律,并且有单位元(空集 $\emptyset$ ),比如 $\cup$ 就是个满足的运算,接下来就用 $\cup$ 来看看。


$$ h=f*g=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ag_Bx^{A\cup B}\\ \Leftrightarrow h_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\cup B=s]f_Ag_B $$

直接做是 $O(4^n)$ 的,很难承受,所以要用到莫比乌斯变换和反演(这就是你叫FMT的理由???)

令 $\hat{f}_A=\sum_{s\subseteq A}f_s$ ,那么根据容斥原理可以得出:$f_A=\sum_{s\subseteq A}(-1)^{|U|-|s|}\hat{f}_s$(集合加来减去那一套)。

听说这货在广义上和数论里的莫比乌斯反演是一样的???(只是听说,错了不要捶我QAQ)

这样的话我们对上面的式子两边变换:

$$ \hat{h}_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\cup B\subseteq s]f_Ag_B\\ \hat{h}_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\subseteq s]f_A[B\subseteq s]g_B\\ \hat{h}_s=\sum_{A\subseteq2^U}[A\subseteq s]f_A\sum_{B\subseteq2^U}[B\subseteq s]g_B\\ \hat{h}_s=\sum_{A\subseteq s}f_A\sum_{B\subseteq s}g_B\\ \hat{h}_s=\hat{f}_s\hat{g}_s $$

你没看错他最后就mogical了……可以直接乘起来啦。

问题是怎么实现莫比乌斯变换和反演,其实变换就是个子集求和,直接上高维前缀和,反演好像就比较奇怪,但是实际上你只要把高维前缀和代码里的 $+$ 改成 $-$ 就好了,因为高维前缀和每次增加一维,增加了之后符号就变了,所以把 $+$ 改成 $-$ 就自动实现了容斥的过程。

这样就可以把复杂度降到 $O(n2^n)$ 了。


然后对于这题,把读进来的 $2^n$ 个数当成集合幂级数 $p$ ,乘法是 $\cup$ 。那么可以得到答案的集合幂级数 $f$ :

$$ f_s=\sum_{k=0}^{+\infty}k(p^{k}_s-p^{k-1}_s)\\ \hat{f}_s=\sum_{k=0}^{+\infty}k(\hat{p}^{k}_s-\hat{p}^{k-1}_s) $$

显然先变换再相减和先相减再变换是等价的,所以上述式子成立。然后开始处理上面的式子,我推了好久以为是什么神仙公式,结果发现这tm就是全列出来之后两项之间消掉变成:

$$ \hat{f}_s=\sum_{k=0}^{+\infty}-\hat{p}^k_s=-\sum_{k=0}^{+\infty}(\hat{p}_s)^k $$

无穷等比数列求和,得到 $\hat{f}_s={1\over\hat{p}_s-1}$ ,注意 $\hat{p}_s=1$ 的时候要特判 $\hat{f}_s=0$ 。最后反演得到 $f$ ,$f_U$ 就是答案。

示例程序

说了这么多,代码其实就是高维前缀和……

#include<cmath>
#include<cstdio>
using namespace std;
typedef double DB;
const int maxn=20,maxs=1<<maxn;

int n;DB p[maxs],f[maxs];

inline void FMT(DB *a,int n,int f){
    for (int i=0;i<n;i++)
        for (int j=0;j<(1<<n);j++)
            if (j>>i&1) f>0?a[j]+=a[j^(1<<i)]:a[j]-=a[j^(1<<i)];
}
inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-10) return 0;return a<b?-1:1;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=0;i<(1<<n);i++) scanf("%lf",&p[i]);FMT(p,n,1);
    for (int i=0;i<(1<<n);i++) if (fcmp(p[i],1)<0) f[i]=1/(p[i]-1); else f[i]=0;FMT(f,n,-1);
    if (!fcmp(f[(1<<n)-1],0)) puts("INF"); else printf("%.10f\n",f[(1<<n)-1]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up