今天学习了一下FWT
你怎么高二了还不会啊
不会这个东西的人已经在这个时代没有人权了23333
教程本来想写的，写到一半就咕咕咕了
反正网上的资料都够多了吧
那么就和FFT一样，整理出一个题表把
用这个异或FWT有一个很重要的思想
就是a^b=c ，那么 a^c=b
这个在构造FWT的时候常常会用到
不说了，看题吧
bzoj 4589: Hard Nim 入门题
考虑到，必胜的情况是所有石子异或起来为0
因此，我们想要知道的就是最后异或为0有多少种方案
每一轮就相当于一次FWT
多堆就是套一个快速幂
bzoj 4036: [HAOI2015]按位或 考虑min-max容斥
我们枚举一个集合，他最早出现的概率就是 1 ? P ( 其 他 位 的 概 率 ) 1-P(其他位的概率) 1?P(其他位的概率)
至于这个 P ( 其 他 位 的 概 率 ) P(其他位的概率) P(其他位的概率)，显然就是一个或卷积的问题了
FWT即可
CF662C Binary Table 挺好的题
考虑n很小
我们不妨爆搜每一个这 n n n行翻转的情况，设为 x x x
然后对于m列，我们都看做一个数， 2 n 2^n 2n的数
设 f i f_i fi?表示 i i i这个数，翻转还是不翻转时候的最优代价
也就是 f i = m i n ( b i n i , n ? b i n i ) f_i=min(bin_i,n-bin_i) fi?=min(bini?,n?bini?)
那么答案显然就是 ∑ f [ a i x o r x ] \sum{f[a_i xor x]} ∑f[ai?xorx]
这样就是 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这个子树，异或起来为 j j j的方案
显然可以用FWT来优化
当然，也可以用点分+树形依赖背包来做
CF453D Little Pony and Elements of Harmony 令 c [ i ] = b [ b i n [ i ] ] 令c[i]=b[bin[i]] 令c[i]=b[bin[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和 j j j卷起来就可以了
可以发现到，每一次卷的 c c c都是一样的
可以用快速幂预处理出来
em…要注意的是，这个模数比较特殊
要先乘 n n n，因为不一定有逆元
那么就要快速乘了。。可以用黑科技 O ( 1 ) O(1) O(1)快速乘
loj #2340. 「WC2018」州区划分 听说叫子集卷积？
感觉很妙啊！！
不难想到 3 n 3^n 3n的DP
然而过不去
如果用卷积优化的话，会出现一个点卷若干次的情况
解决方法是，对于每一个状态多记录一维，表示有多少个点，这样就不会出现一个点算多次的情况了
那么 f [ n ] [ 1 <
<
n ? 1 ] f[n][1<
<
n-1] f[n][1<
复杂度是 2 n ? n 2 2^n*n^2 2n?n2的
【高二生活|FWT 题表】大概就先写着这么多吧。。
相信大家做完这个题表也可以对FWT有一个初步的认识了
那么，就以后见到什么经典的再写吧
