昨天考试由于不会fwt而爆炸,所以今天搞了一下fwt……话说这玩意的普及程度已经很高了.
fwt,快速沃尔什变换,可以用于位运算卷积的优化,是一种线性变换,所以就会有许多好的性质(eg:可以直接模,可以修改运算等). & | ^ 的变换定义与方法是基础,在此基础上的扩展与运用是重要的地方.
HZOI #1572.宇宙序列
notes:
这就是造成我考试爆炸的考试题,见Contest Record
UOJ #310.【UNR #2】黎明前的巧克力
notes:
感觉比较灵活的一道题.首先写出裸dp,之后会发现答案就是许多数组连续进行fwt,这个时候经过观察会发现,每个数组变换后每个位置上不是-1就是3这个时候我们可以对于每一位进行单独考虑,去算与这一位&之后有奇数位的数的个数,以及与这一位&之后有偶数位的数的个数,我们可以用fwt计算这个,然后计算每一位的最后答案,最后再ifwt回去.
思想:
I.感觉在fwt里利用对应位相乘所导致的每一位互相独立是许多fwt题目中解题的关键.
II.在这个题目中观察性质从而改变问题的思路很巧妙啊.
UOJ #267.【清华集训2016】魔法小程序
notes:
就是对于|运算fwt的扩展,看懂题意之后其实就是个加工板子的过程.不过,感觉那个数据范围给的好迷啊,为什么int就可以呢……不会证明……
UOJ #300.【CTSC2017】吉夫特
notes:
题目比较傻逼,首先可以写出n^2裸dp来,然后用Lucas定理可以证明出,一个组合数为奇数的充要条件,然后就可以枚举子集来dp了,是O(3^18).
实际上这题可以做得更加优秀.
首先这题可以进行序列上的分块,做到O(2^27).
然后这道题还可以用二进制分块来动态维护&运算fwt数组,从而做到O(6^9).
思想:用Lucas定理来进行组合数相关的证明(我反正是没想到这玩意)、分块思想(序列分块、二进制分块).
技巧:枚举子集是i=(i-1)&x,枚举父集是i=(i+1)|x.
UOJ #348.【WC2018】州区划分
notes:
先写出O(3^n)的傻逼dp,然后开始优化.
发现转移是子集卷积的形式,于是考虑进行子集卷积,然后这题就完事了.
子集卷积:
f(i)=sigma [j|k=i,j&k=0] g(j)*h(k);
转化为f(c,i)=sigma [j|k=i,|j|+|k|=c] g(j)*h(k)
这个时候我们原来的子集卷积,就变为了二维卷积(也就是加法卷积套|运算卷积),显然第一维卷积可以直接计算,第二维卷积fwt就可以了,于是子集卷积的复杂度从O(3^n)优化到了O(n^2*2^n).