UOJ Logo liu_runda的博客

博客

不会FWT的选手计算集合并卷积的方法(UPD:博主智商着急了)

2017-02-25 16:12:00 By liu_runda

UPD:智商着急现场...这个做法其实就是vfk论文的快速莫比乌斯变换......并不是什么新做法.....我是文盲...

给出$f[0..(2^n)-1],g[0..(2^n)-1]$,求$h[0…(2^n)-1]$,满足h[x]=sigma{f[i]*g[j],1<=i<=n,1<=j<=n,i|j==x}

N<=20

传说中的集合并卷积?作为不会FWT的选手,我们考虑如何写暴力.

暴力算法1:枚举i和j更新h[i|j]可以做到O(4^n).

暴力算法2:容斥原理+枚举子集的子集可以做到O(3^n)

我们记F[i]=sigma(f[j],j&i==j),G[i]=sigma{g[j],j&i==j},H[i]=F[i]*G[i],那么H[i]=sigma{h[j],i&j==j}, 通过枚举子集的子集可以O(3^n)得到H[]数组,通过枚举子集的子集可以O(3^n)用H[]数组容斥出h[]数组,求 h[i]的时候,枚举i的所有子集,如果子集j的元素个数和i相差偶数个那么H[j]对h[i]的贡献是正的,如果子集j的元素和i相差奇数个那么H[j]对h[i]的贡献是负的.

也就是说: h[i]=sigma{H[j]*(-1)^(cnt1(i-j)),j&i==j},cnt1(x)表示x的二进制表示中1的个数

接下来我们把O(3^n)的容斥算法优化到O(n*2^n).

考虑第一步预处理,我们需要求出F[x]=sigma(f[i],i&x==i)(G数组的处理和F数组相同) 如果我们求出了1到x-1的F值,并不能利用前面这些项较快地计算出F[x]。

不妨考虑x的最高位2^i,我们把x的子集分成两部分,一部分包含元素i,一部分不包含元素i,不包含元素i的部分就是F[x-(2^i)],关键是包含i的部分.我们无法从F[1],F[2],…一直顺序推到F[2^n-1]

我们记F[j][i]为只允许最后j位和i不同的i的所有子集的和,那么边界是F[0][i]=f[i] F[j][i]=F[j-1][i](i的第j位为0) =F[j-1][i]+F[j-1]i-(2^j) 前一维可以直接滚掉,那么我们就用O(n*2^n)的时间解决了F数组和G数组

for(int j=0;j<n;++j){
    for(int i=0;i<lim;++i){
        if((i>>j)&1)f[i]+=f[i^(1<<j)];
    }
}

(其实是一个n维前缀和?这个技巧是以前别人讲课的时候看见的) 接下来考虑H数组.我们发现从H数组求h数组相当于从F数组求f数组,我们把之前的DP过程倒过来就可以了…就是加号改成减号…因为每个二进制位本质一样所以从高位向低位枚举还是从低位向高位枚举都一样.

这个地方也可以理解为,h[j][i]为只允许最后j位和i不同的i的所有子集对i的贡献之和,

边界是 $h[0][i]=f[i]$

$h[j][i]=h[j-1][i](i的第j位为0)$

$h[j][i]=h[j-1][i]-h[j-1][i-(2^j)](i的第j位为1)$ 可以理解为每增加一个二进制位会使贡献的正负号改变一次所以把加号变成减号.

然后这个方法并没有什么可扩展性,只能算集合并卷积。

下面这个代码是mod 2^32意义下的,利用unsigned int自然溢出

#include<cstdio>
#include<cctype>
typedef unsigned int u32;
void read(u32 &x){
    char ch;while(ch=getchar(),!isdigit(ch));x=ch-'0';
    while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
}
const int maxn=1<<20;
u32 f[maxn],g[maxn];
u32 H[maxn];
int main(){
    freopen("evaluation.in","r",stdin);
    freopen("evaluation.out","w",stdout);
    u32 n;read(n);int lim=1<<n;
    for(int i=0;i<lim;++i){
        read(f[i]);
    }
    for(int i=0;i<lim;++i){
        read(g[i]);
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<lim;++j){
            if((j>>i)&1)f[j]+=f[j^(1<<i)];
        }
      }
    for(int i=0;i<n;++i){
      for(int j=0;j<lim;++j){
          if((j>>i)&1)g[j]+=g[j^(1<<i)];
      }
     }
    for(int i=0;i<lim;++i)H[i]=f[i]*g[i];
    for(int i=0;i<n;++i){
        for(int j=0;j<lim;++j){
            if((j>>i)&1)H[j]-=H[j^(1<<i)];
        }
    }
    u32 ans=0;
    for(int i=0;i<lim;++i){
        ans+=H[i]*(i+1);
    }
    printf("%u\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

评论

liu_runda
其实题目应该叫不会markdown的选手写博客的方法...啥也不说了我接着排版...
SNKMODE
= =,这玩意vfk的论文里头有写= =?
JOHNKRAM
=_=这不就是FWT的非递归形式吗……
WrongAnswer
以前觉得集合并卷积是个很高端的东西,照着论文的证明写了一遍后来就忘了。清华集训day1我在做第2题的时候,一开始掉坑,列的是容斥的式子,想到了卷积以及{F*T}……很快我觉得肯定不是这么做,就放弃了这个思路。 对着式子看了发现符号是不断取反加在后面的(其实就是容斥),于是按维直接前缀和以及直接差分好像就是对的了。比如前缀和,相当于先处理一维前缀和,再处理二维前缀和…… 出考场以后和immortalCO讨论,immortalCO说这题就是个裸的FMT(FWT是异或卷积,这个应该叫莫比乌斯变换FMT),果然我还是太naive了…… 不过这么说来我也总结了一个东西:集合并卷积就是 $n$ 维前缀和,可以在 $O(2^nn)$ 的时间内完成。
WrongAnswer
(字数限制)FMT卷积我是这么理解的:如果记 $S(x)=\sum_{i\cup j\subseteq x}f(i)g(j)=\sum_{i\subseteq x}f(i)\sum_{j\subseteq x}g(j)$,那么 $S(x)=\sum_{y\subseteq x}h(y)$。 做的时候,先求 $F(x)=\sum_{x'\subseteq x}f(x)$,$G(x)=\sum_{x'\subseteq x}g(x)$,这就相当于多维前缀和。 令 $S(x)=F(x)G(x)$ 以后求 $h(x)$ 就相当于多维差分。 所以FMT的过程可以认为是做两次前缀和和一次差分。 可以想象两个长度为 $n$ 的一维数组 $a,b$,求 $c_i=\sum_{\max\{j,k\}=i}a_jb_k$,如果画一个 $n\times n$ 的表格,$(i,j)$ 格子填的数是 $a_ib_j$,那么 $c_i$ 就是 $i$ 和 $i-1$ 两个前缀正方形的差,对 $a,b$ 求前缀和把前缀和的积存到 $c$ 里面再对 $c$ 差分就做完了。
indogent
(字数限制)FMT卷积我是这么理解的:如果记 [Math Processing Error],那么 [Math Processing Error]。 做的时候,先求 [Math Processing Error],[Math Processing Error],这就相当于多维前缀和。 令 [Math Processing Error] 以后求 [Math Processing Error] 就相当于多维差分。 所以FMT的过程可以认为是做两次前缀和和一次差分。 可以想象两个长度为 [Math Processing Error] 的一维数组 [Math Processing Error],求 [Math Processing Error],如果画一个 [Math Processing Error] 的表格,[Math Processing Error] 格子填的数是 [Math Processing Error],那么 [Math Processing Error] 就是 [Math Processing Error] 和 [Math Processing Error] 两个前缀正方形的差,对 [Math Processing Error] 求前缀和把前缀和的积存到 [Math Processing Error] 里面再对 [Math Processing Error] 差分就做完了。
indogent
深刻论证楼上毒性十足 证法如下: [Math Processing Error] [Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error] [Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error][Math Processing Error] [Math Processing Error][Math Processing Error]

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。