di_z

题解 FWT推导 + Codeforces 1119H 题解

题解

/ 注册

FWT推导 + Codeforces 1119H 题解

1208 浏览 0 回复 2019-07-26

di_z

+关注

Problem - H - Codeforces

http://codeforces.com/contest/1119/problem/H

题目描述

有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$

题解

代码

FWT

举报

收藏

赞

评论加载中...