[ 2019牛客暑期多校训练营(第一场) ] D Parity of Tuples

题目大意:有n个m元组\(v_1, v_2, \cdots, v_n\),第i个m元组\(v_i = a_{i,1}, a_{i,2}, \cdots , a_{i,m}\)。定义\(count(x)\)为这n个m元组中,对所有\(j = 1 \cdots m\)满足\(a_{i,j} \oplus x\)的二进制表示中有奇数个1的m元组的个数。求\(count(x), x = 0 \cdots 2^k – 1\),其中\(1 \leq n \leq 10^5\),\(0 \leq a_{i,j} < 2^k\),\(1 \leq k \leq 20\),\(1 \leq m \leq 10\)。

题解:观察FWHT中的Haramard矩阵,\(H_{ij}=(-1)^{count1(i\ and\ j)}\),其中\(count1(x)\)表示x的二进制表示中1的数量;这和我们题目中要的东西很像。关于这道题目,我们可以发现我们并不需要做什么卷积;也就是说,我们其实并没有在做一个完整的FWHT。做这道题主要用到的是FWHT中的那个Haramard变换矩阵,然后我们有方法在和这个矩阵做矩阵乘法的时候把时间复杂度降到\(O(n\log (n))\),所以做这道题只需要知道\(H_{ij}=(-1)^{count1(i\ and\ j)}\),然后贴个FWHT的板子使做该矩阵乘法的时间复杂度降到\(O(n\log (n))\)就好了(完全不知道WHT是啥的也可以先看一下http://www.zarxdy34.top/?p=203来帮我增加一下访问量)。

为了方便起见,设\(f(x)=(-1)^{count1(x)}\),即x二进制表示下有奇数个1时为-1,偶数个1时为1,\(H_{ij}=f(i \oplus j)\)。由于有如下性质:

\[ \begin{aligned}
H_{t(x \oplus y)} &=(-1)^{count1(t\ and (x \oplus y))} \\
&= (-1)^{count1((t\ and\ x) \oplus (t\ and\ y)) – 2k} \\
&= (-1)^{count1((t\ and\ x) \oplus (t\ and\ y))} \\
&= H_{tx} \cdot H_{ty} \end{aligned} \]

所以有\(f(x \oplus y) = f(x) \cdot f(y)\)。

设向量\(X=(X_0,X_1,\cdots,X_{2^k-1})\),考虑\(Y=H \cdot X\),有

\[Y_i = \sum_{j=0}^{2^k-1}{H_{ij} \cdot X_j}\]

即如果\(f(i \oplus j)=1\),则向量\(X\)对\(Y_i\)的贡献加上\(X_j\),否则减去\(X_j\)。

现在固定x=t,考虑每一个m元组的生成函数\(F_i\),我们想要让\( \lbrack x^t \rbrack WHT(F_i) = 1\)(也就是\(H \cdot F_i\)所得向量的第t项)当且仅当对所有\(j = 1 \cdots m\)有\(f(a_{i,j} \oplus u) = -1\),即如果有一个\(count1(a_{i,j} \oplus u)\)为偶数则贡献为0。要让该式子对\( \lbrack x^t \rbrack WHT(F_i)\) 贡献为1很难做到(其实也不难,就是下面那个东西除以\(2^m\)),但是我们只要做到让它的贡献为与\(a_{i,j}\)无关的一个定值就可以了。设\(b_j=-f(a_{i,j} \oplus u)\),构造式子

\[(1+b_1) \cdot (1+b_2) \cdot (1+b_3) \cdot \cdots \cdot (1+b_m)\]

只要其中出现了一次\(b_j=-1\),即某个\(a_{i,j} \oplus u\)中1的个数为偶数时,该式的值即为0;否则,该式值恒为\(2^m\)。

对于式子中的\(b_j\),我们对该式的生成函数\(F_i += (-1) \cdot x^{a_j}\),对应位置上就加上了\(b_j\)的贡献。但式子展开后还有一个常数项以及若干个\(b_{jk}\)的乘积,至于\(b_{j1} \cdot b_{j2}\)之类的项,由于有如下性质:

所以可以发现,\(b_{j1} \cdot b_{j2}\)对应的项是\(x^{a_{i,j1} \oplus a_{i,j2}}\),系数就是它们的乘积,(单个为-1,所以两个异或起来的就是1,三个则是-1,依次类推),常数项对应一个都不取的情况。

由于FWHT是一个线性运算,所以可以把每个m元组,甚至每个m元组中的每一项的贡献单独计算并相加,所以就可以直接先把所有项全部加起来然后直接做一次FWHT得出答案。


page views : 31 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注