AntiLeaf的博客

博客

2018-01-22 17:43:43 By AntiLeaf

有一天自己想FWT的时候冒出来的问题

FWT_or实际上在干这样的事情

$F W T (f) (S) = \sum_{T \subset S} f (T)$

如果把求和换成min也是可以的

同时如果要求

$h (S) = \sum_{T \subset S} f (T) g (S - T)$

的话也不难搞

那么问题来了，如果要求

$h (S) = min_{T \subset S} {f (T) + g (S - T)}$

呢？QAQ

UPD：

博主制杖了……似乎

$h (S) = \sum_{T \subset S} f (T) g (S - T)$

也不好弄的样子……

前者是因为子集和变换只要用加法吧，xor的FWT要减法所以gg了吧。。

评论回复
liu_cheng_ao：应该说是IFWT要减法吧…… 2018-02-12 14:13:05 回复

不知道

h (S) = \sum_{T \subset S} f (T) g (S - T)

具体是怎么做的诶，能不能简单解释一下？

评论回复
AntiLeaf：窝好像脑子短路了QAQ……之前想的做法是错的 2018-01-27 19:57:25 回复
riteme：回复 @AntiLeaf：QAQ不会这样吧... 2018-01-27 22:37:22 回复
krydom：按二进制内1的个数拆分每个做一遍fwt再卷积一下？ 2018-01-29 21:20:24 回复
WuHongxun：回复 @krydom：为什么我被downvote了啊 2018-01-29 22:08:10 回复
riteme：回复 @krydom：好像可以诶，是两个log的吗？ 2018-01-30 12:53:51 回复

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。