【知识&题解】UOJ310题解&FWT相关知识概述

总述

  就我现在的理解,FWT过程可以通过两种看上去不太一样的做法来实现(本质可能是一样的)。
  一种在pick's blog上有介绍,是基于FFT模式和构造。
  另一种可以参见2015年VFK的集训队论文,是基于推公式和DP。
  总的来说,我喜欢VFK的这种套路,他对于三种基本逻辑运算(or,and,xor)都有不同的公式推导,而且感觉更可以推广;不过pick's的构造套路更加适合记忆,特别是在他的系统里,这些运算是可以统一成几乎一样的代码。
  以下主要是根据VFK的论文来重点讲述集合xor的卷积。

模型的描述

  我们要在较短的时间内求两个集合的对称差卷积,即
  $$F_S=sumlimits_{L|U} {sumlimits_{R|U} {[A⊕B=S] imes A_L imes B_R}}$$

基于xor的FWT的过程

  给出一个集合函数 (F_S) ,那么我们定义 (FWT(F)) 为求集合函数 (F'_S) 的过程,使得:
  $$F'S=sumlimits{T|U} {F_T(-1)^{|S∩T|}}$$
  而且,(FWT(S)^{-1})过程(即将F'还原成F)相应是这样:
  $$F_S=frac{1}{2^n} sumlimits_{T|U} {F'_T(-1)^{|S∩T|}}$$
  这样定义有啥好处呢?
  那么我们有结论:
  $$F'_S=A'_S*B'_S$$
  这样,只需先将A和B逆一下,然后线性求积,再逆回来。具体证明可以参加VFK的论文。

一道很不错的UOJ例题

【题目大意】

  给出 (N(N leq 10^6)) 个数字,两个人来选。每一个人各选出一个数字( $S leq 10^6 $ )集合(集合不能相交)。问两个人取的数字的异或和正好相等的方案数(模一个NTT质数)。

【考虑直接DP】

  设 (f_{i,j}) 表示考虑到第i个数字,目前两人的异或和是j的方案数。对于 (a_{i+1}) ,如果没有人选,就是 (f_{i+1,j} leftarrow f_{i,j}),如果选,就是 $f_{i+1,j oplus a_{i+1}} leftarrow 2f_{i,j} $ (因为两个人都可以选)。这样就是简单无脑的 (S^2) 做法啦!

【用xor卷积的知识来暴力转化】

  先要暴力地想,对于每一个(a_{i+1}),我们可以暴力开一个数组 (G),满足 (G_0=1,G_{a_{i+1}}=2),然后 (F_{i+1}=F_{i} oplus G)(上述粗体的模型)。
  只是,这样太浪费了,效率也更低了。

【优化xor卷积】

  本质上,我们是想快速求得 (F)(G) 啊这些函数的反演形态(因为我们是用反演形态相乘的嘛)。
  根据反演的定义,我们可以知道,(G) 函数每一个位置都只有 (3)(-1) 两种数值(直接带入求 (G’) 的式子里即可发现)。而且,这是由下标 (k)(a_{i+1})(and) 值的位数的奇偶性决定的。我们的最终目标,就是对于每一个下标 (k),求出那么多 (G) 的这一位的乘积。
  换一个想法,假设我们可以 (O(1)) 知道每一个 (G') 某一个下标位置 (i) 的数值之和,那么我们可以通过解方程来确定这个下标有多少个 (G')(3),多少个G'是 (-1),这样也就能用快速幂来求得这一个位置的乘积了。那么如何求和呢?
  我们要求的 (Sum_k) 满足 $ Sum_k=n+2*sumlimits_{i=1}^n {-1^{|a_i & k|}} $
  仔细观察这个式子,这不就和反演的定义式一样吗!现在,我们只需统计 (n) 个数字中数字 (i) 出现了多少次,代入FWT过程,即可求出所有的 (Sum_k) !
  至此所有的问题都解决了,效率也就是 (O(S log S)),也即是(O(2^n imes n))

原文地址:https://www.cnblogs.com/jiangshibiao/p/7173026.html