@xzyxzy 2018-07-20T23:41:23.000000Z 字数 807 阅读 2885

高维前缀和

动态规划

作业部落

高维前缀和是个好东西，很多人把它归类为状态压缩 $DP$ ，其实听说它是由 $FWT$ 衍生出来的黑科技？

求x二进制下的超集或子集的所有状态之和怎么办？
（如 $0101$ 超集为 $0101,1101,0111,1111$ ,子集为 $0101,0001,0100,0000$ ）
高维前缀和可以把这个过程从 $2^n×2^n$ 优化到 $n×2^n$ ( $2^n$ 为最大值域范围)

通过高维前缀和的枚举顺序，可以保证枚举到第 $i$ 位的 $1$ ，所有第 $i+1$ 到末位的数的超集（子集）情况都被涵盖在内，具体原理理解请照代码手玩 $0-7$ （博主就是靠这个理解的，但是太懒不想做表了，毕竟还有辣么多东西还没学还没总结）

for(int j=0;j<n;j++)
    for(int i=0;i<1<<n;i++)
        if(!(i&(1<<j))) f[i]+=f[i|(1<<j)];

for(int j=0;j<n;j++)
    for(int i=0;i<1<<n;i++)
        if(i&(1<<j)) f[i]+=f[i],f[i^(1<<j)];

这里可以自定义运算，可以取最值等等
$Update7.21$ :其实求超集就是 $FWT\_or(f,1)$ ,求子集就是 $FWT\_and(f,1)$

很多情况需要求的是恰好怎样的答案，这个时候可以改为至少怎样的方案，然后用 $\pm1$ 容斥或者组合数容斥解决
$eg:$ 考试2018.7.9T1、[CF449D]Jzzhu and Numbers

可以考虑 $01$ 翻转后计算贡献
$eg:$ [SPOJ2829]Time Limit Exceeded