家具行业做那个国际网站比较好,网站制作网络推广关键词排名,外贸公司网站设计哪家好,广州网站优化系统昨天考试由于不会fwt而爆炸,所以今天搞了一下fwt……话说这玩意的普及程度已经很高了.fwt,快速沃尔什变换,可以用于位运算卷积的优化,是一种线性变换,所以就会有许多好的性质(eg:可以直接模,可以修改运算等). | ^ 的变换定义与方法是基础,在此基础上的扩展与运用是重要的…昨天考试由于不会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(i1)|x. UOJ #348.【WC2018】州区划分 notes: 先写出O(3^n)的傻逼dp,然后开始优化.发现转移是子集卷积的形式,于是考虑进行子集卷积,然后这题就完事了.子集卷积: f(i)sigma [j|ki,jk0] g(j)*h(k); 转化为f(c,i)sigma [j|ki,|j||k|c] g(j)*h(k) 这个时候我们原来的子集卷积,就变为了二维卷积(也就是加法卷积套|运算卷积),显然第一维卷积可以直接计算,第二维卷积fwt就可以了,于是子集卷积的复杂度从O(3^n)优化到了O(n^2*2^n). 转载于:https://www.cnblogs.com/TSHugh/p/8897926.html
