2019-07-26 21:33 已编辑中山大学 C++

关注

FWT推导 + Codeforces 1119H 题解

题目描述

有n个数组，第i个数组由 $a_i$ 个 $x$ , $b_i$ 个 $y$ , $c_i$ 个 $z$ 组成，在每个数组中选出一个数，然后xor起来等于t，求方案数。对全部的 $t\in [0, 2^k-1]$ 输出答案。

分析

题目等价于询问将n个这样的数组作xor卷积的结果： $a_i$ 位置为 $x$ , $b_i$ 位置为 $y$ , $c_i$ 位置为 $z$ ，其余位置为0.

简化问题，先将所有 $a_i$ xor起来作为结果，然后，bi^=ai, ci^=ai

问题转化成n个这样的数组作xor卷积：0位置为 $x$ , $b_i$ 位置为 $y$ , $c_i$ 位置为 $z$ ，其余位置为0.

为了得到这题正解，我们得明白FWT的推导过程。

FWT 推导

FWT需要解决的是这样一个xor卷积问题：

$C_x=\sum_{i \bigoplus j=x}A_iB_j$

我们目标是寻找一个线性变换FWT，令 $FWT(F)$ 满足

$FWT(C)_x=FWT(A)_xFWT(B)_x$

既然是线性变换，就可以表示成矩阵 $g(x,i)$ ,使得

$FWT(F)_x=\sum^{n}_{i=0} g(x,i)F_i$

我们的目标可以表示成

$\sum^{n}_{i=0} g(x,i)C_i = \sum^{n}_{j=0} g(x,j)A_j \sum^{n}_{k=0} g(x,k)B_k$

将 $C_x=\sum_{i \bigoplus j=x}A_iB_j$ 代入，

$\sum^{n}_{i=0} g(x,i)\sum_{j \bigoplus k=i}A_jB_k = \sum^{n}_{j=0} g(x,j)A_j \sum^{n}_{k=0} g(x,k)B_k$

化简得，

$\sum^{n}_{j=0}\sum^{n}_{k=0} g(x, {j \bigoplus k})A_jB_k = \sum^{n}_{j=0}\sum^{n}_{k=0} g(x,j)g(x,k)A_j B_k$

也就是，

$g(x, {j \bigoplus k})=g(x,j)g(x,k)$

考虑 $j\bigoplus k$ 的什么属性会是 $j,k$ 属性的乘积.

对于异或操作来说，异或前后1的个数的奇偶性不会改变，也就是说 $j,k$ 中1的个数加起来和 $j\bigoplus k$ 中1的个数的奇偶性是一样的。

于是我们可以定义

$g(x,i)=(-1)^{|i\cap x|}$

每一项其实是二进制表示的集合，因此使用集合交符号 $\cap$ 与集合大小符号|S|

所以FWT就是

$FWT(F)_x=\sum^{n}_{i=0}(-1)^{|i\cap x|}F_i$

题解

代码

Submission

全部评论

推荐最新楼层

不愿透露姓名的神秘牛友

07-11 17:10

花钱改简历被骂了

什么素质，我请问呢，要掉小珍珠了。。。又憋屈又生气

Steven267：这不喷回去？花钱是大爷，记住这个道理

点赞评论收藏

07-09 13:51

门头沟学院 Java

秋招这就要开始了吗

还处在暑期实习上岸后的摆烂状态实习：杂活多，产出少，文档也没偷学多少八股：忘的差不多了项目：有实习就不会问玩具项目了吧力扣：我可以说我连hot 100都没刷完吗国企：从零开始准备论文：没着落

回收旧报纸：世另我，只是我比你更烂一些，没找到实习，你起码还有实习的，秋招猛猛冲，加油

点赞评论收藏

07-10 14:08

已编辑

江西农业大学 Java

笔试做项目

咋感觉是白嫖呢

念旧select：做完把项目放到自己硬盘里给他看，看完拷走

点赞评论收藏

06-03 11:31

四川轻化工大学 Java

大三找实习，大家可以给点意见吗，这个简历有什么问题

不想上班的芝士很想居...：smm是什么技术

实习，投递多份简历没人回...

点赞评论收藏

07-12 10:49

北京邮电大学产品经理

滴滴秋招提前批产品岗位放出，我的一些解读

昨天，我的老东家滴滴，终于在官方公众号发布了 26 届秋招提前批。岗位投递任意门岗位涉及工程、算法、机器人、数据、产品、安全、金融、运营、商分多个岗位类型，无需笔试，直接面试。本次秋招释放的产品岗位全部来自滴滴国际化事业部。滴滴国际化业务范围主要包含出行、外卖和金融服务，在巴西、墨西哥等国区国际化业务都有不错的市占表现，是滴滴近年来规模稳定增长的重要支撑。这次外露的产品岗位类型包括四大类：用户增长、B 端方向、金融/支付/信贷、综合产品需要特别关注这些产品岗位秋招提前批每个简历只能投递一次以下是岗位解读，如有面试准备/复盘需要可私想做面试准备，最好的办法就是勤练习，多复盘！用户增长类产品助理涉...

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 如果公司给你放一天假，你会怎么度过？ #