今天学习了FWT
你怎么高二了还做不到
做不到这一点的人已经在这个时代没有了人权23333
我想写教程，但是写到一半就发牢骚了
反正网上的资料足够了吧
那么，就像整理FFT一样，整理问题列表
在这个异或FWT中有重要的思想
a^b=c，a^c=b
这在构建FWT时经常使用
别说了，看问题吧
bzoj 4589: Hard Nim入门问题
考虑到，必胜时所有石头的异或都为0
因此，我想知道最后的异或为0有多少个方案
相当于一回合一次的FWT
山多就是乘以快乘方
考虑bzoj 4036: [HAOI2015]分位或最小最大容忍
我们列举集合。 他首先出现的概率是1p (其他比特的概率)1-P (其他比特的概率) 1p (其他比特的概率) )
p (其他位置的概率) p (其他位置的概率) p (其他位置的概率)显然是卷积问题
FWT就可以了
cf 662 c二进制表是个非常好的问题
认为n小
让我们搜索这n n n行中每个反转的情况，并将其作为x x x
而对于m列，均取1个数，2n2￣n2n数
假设f i f_i fi表示i i i这个数，表示是否反转的最佳代价
也就是说，fI=mIn(bInI，nbini ) f_I=min ) n-cjdxmg_i，n-cjdxmg_i ) fi=min ) ncjdxmgi，ncjdxmgi )
答案显然是f
[ a i x o r x ] sum{f[a_i xor x]} ∑f[aixorx]这样就是 2 n m 2^nm 2nm了
似乎没什么好优化的
记得上面说的套路吗？
我们尝试通过预处理，算出每一个 x x x的答案
可以发现，我们把 f f f和原来的字符异或卷积起来就可以了 hdu 5909 Tree Cutting
可以直接DP
f i , j f_{i,j} fi,j表示 i i i这个子树，异或起来为 ssdyf的方案
显然可以用FWT来优化
当然，也可以用点分+树形依赖背包来做
CF453D Little Pony and Elements of Harmony 令 c [ i ] = b [ b i n [ i ] ] 令c[i]=b[cjdxmg[i]] 令c[i]=b[cjdxmg[i]]
f [ i ] = ∑ c [ i ⊕ j ] ∗ f [ j ] f[i]=∑c[i⊕j]∗f[j] f[i]=∑c[i⊕j]∗f[j]
那么同样的，把 c c c和 ssdyf卷起来就可以了
可以发现到，每一次卷的 c c c都是一样的
可以用快速幂预处理出来
em…要注意的是，这个模数比较特殊
要先乘 n n n，因为不一定有逆元
那么就要快速乘了。。可以用黑科技 O ( 1 ) O(1) O(1)快速乘
听说叫子集卷积？
感觉很妙啊！！
不难想到 3 n 3^n 3n的DP
然而过不去
如果用卷积优化的话，会出现一个点卷若干次的情况
解决方法是，对于每一个状态多记录一维，表示有多少个点，这样就不会出现一个点算多次的情况了
那么 f [ n ] [ 1 < < n − 1 ] f[n][1<<n-1] f[n][1<<n−1]一定是只有n个点的，也就是一定是合法的
然后就可以了
复杂度是 2 n ∗ n 2 2^n*n^2 2n∗n2的
大概就先写着这么多吧。。
相信大家做完这个题表也可以对FWT有一个初步的认识了
那么，就以后见到什么经典的再写吧