[ Codeforces Global Round 2 ] [ CF 1119H ] Triple

题目大意:给出\(x,y,z(0 \leq x,y,z \leq 10^9)\)以及\(n\)个三元组\((a,b,c)(0 \leq a,b,c < 2^k,,1 \leq k \leq 17)\),\(a,b,c,x,y,z\)都是整数,第i个三元组\((a_i, b_i, c_i)\)对应着一个含有\(x\)个\(a_i\),\(y\)个\(b_i\),\(z\)个\(c_i\)的数组。现在要从每个数组中取出一个数,求取出所有数的异或值为\(0…2^k-1\)中的每一个数的方案数。

题解:初看题目应该能想到FWHT,但是FWHT显然不能直接做,需要优化。

考虑第\(i\)个数组的生成函数\(F_i\),有\[ [x^{a_i}]F_i = x, [x^{b_i}]F_i = y, [x^{c_i}]F_i = z\]

答案即为所有\(F_i\)的异或卷积。直接用FWHT的时间复杂度为\(O(2^k n \log n\)),显然是不行的。

要对这个优化,首先得对FWHT有足够充分的理解。从FWHT(Fast Walsh-Hadamard Transform)的本质考虑,他是将原多项式进行了一次线性变换,经过该线性变换后多项式由系数表达转为了点值表达(这一点和FFT是一样的),即

\[WHT(F_i) = H \cdot F_i\]

其中\(F_i\)是一个n*1的向量,向量值为系数,H是变换矩阵(WHT中的Haramard matrix),其中\(H_{ij} = (-1)^{count(i\ and\ j)}\),可见H中只有1和-1两个值,而因为\(F_i\)中也只有\(x,y,z\)三个数,所以\(WHT(F_i)\)中也只有8个数:

\[x+y+z,x+y-z,x-y+z,x-y-z, \\
-x+y+z,-x+y-z,-x-y+z,-x-y-z\]

举一个简单的例子,考虑\(k=2\)时,\(F_i=(x,0,y,z)^T\),H矩阵为

\[H=\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1
\end{pmatrix}\]

则\(WHT(F_i)\)等于

\[WHT(F_i)=H \cdot F_i = \begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1
\end{pmatrix} \begin{pmatrix}
x\\
0\\
y\\
z
\end{pmatrix} = \begin{pmatrix}
x+y+z\\
x+y-z\\
x-y-z\\
x-y+z
\end{pmatrix}\]

显然可见,k足够大的时候,8种情况都是有可能出现的,并且由于\(x,y,z\)对于所有数组来说都是一样的,所以每个数组的生成函数经过WHT变换后都是只有这8个数。对于某个固定的异或结果\(t\)有

\[ [x^t](\prod{WHT(F_i)}) = (x+y+z)^{a_0} \cdot (x+y-z)^{a_1} \cdot (x-y+z)^{a_2} \cdot \cdots \cdot (-x-y-z)^{a_7}\]

直接将\(n\)个数组生成函数做FWHT效率低下之处从这里就可以看出来了。如果对于每个\(t\),我们都能\(O(1)\)算出其对应的\(a_0,a_1,a_2, \cdots ,a_7\),那么显然我们就可以花\(O(2^k)\)的时间(忽略快速幂的时间)将每个答案直接求出来。

为此,首先我们需要理解这样一件事情:由于WHT是一个线性变换,所以可以得到如下式子:

\[ \begin{aligned}
WHT(\sum{F_i}) &= H \cdot \sum{F_i} \\
&= \sum{H \cdot F_i} \\
&= \sum{WHT(F_i)}
\end{aligned}
\]

所以有

\[ \begin{aligned}
\lbrack x^t \rbrack WHT(\sum{F_i}) &= \sum{[x^t]WHT(F_i)} \\
&= a_0(x+y+z) + a_1(x+y-z) + \cdots + a_7(-x-y-z)
\end{aligned}
\]

注意这里\( WHT(\sum{F_i}) \)并没有实际意义(就我知道的来说),但是它可以帮助我们求出\(a_0 \cdots a_7\)的值。因为我们可以在\(O(n)\)的时间内求出\(\sum{F_i}\),并在\(O(n\ log \ n)\)的时间内求出\(WHT(\sum{F_i})\),由此我们可以得到关于\(a_0 \cdots a_7\)的一个方程。但是我们未知数的数量有8个,需要8个方程才能解出来,那么剩下的方程怎么来呢?

从这里我们应该开始意识到这样的一件事情:无论\(x,y,z\)的取值为多少,\(a_0 \cdots a_7\)的值都是不会变的,和\(x,y,z\)无关。这样一来,我们就可以对\(x,y,z\)任意取值来得到多个方程。但即使如此,我们也只能得到三个线性无关的方程(只有\(x,y,z\)三个变量)。为了得到8个方程,显然我们不能仅依赖于\(x,y,z\)这三个变量;也就是说,从现在开始,为了解出\(a_0 \cdots a_7\),我们要明确这么一件事情:\(a_0 \cdots a_7\)的值到底和什么有关?

考虑\(x,y,z\)的取值,如果取\(x=1,y=0,z=0\),即\(F_i=x^{a_i}+0x^{b_i}+0x^{c_i}\),则有

\[a_0+a_1+a_2+a_3-a_4-a_5-a_6-a_7=[x^t]WHT(\sum{F_i})\]

取\(x=0,y=1,z=0\),即\(F_i=0x^{a_i}+x^{b_i}+0x^{c_i}\),则有

\[a_0+a_1-a_2-a_3+a_4+a_5-a_6-a_7=[x^t]WHT(\sum{F_i})\]

\(x=0,y=0,z=1\),则有

\[a_0-a_1+a_2-a_3+a_4-a_5+a_6-a_7=[x^t]WHT(\sum{F_i})\]

这就是目前我们能够得到的三个方程。

另外一个显而易见的方程是,考虑到\([x^t]WHT(\sum{F_i})\)是n个\(x,y,z\)的组合相加得到的,有:

\[a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7=n\]

可以推测一下这个式子是如何得到的,考虑\(a_i=0 (i=1\cdots n) ,x=1,y=0,z=0\)的情况,此时每一项\([x^t]WHT(F_i)\)中x的系数肯定是1,因为\(H_{ij}=(-1)^{count(i\ and\ j)}\),无论\(t\)是多少,由于\(a_i=0\),\(H_{t0}=1\),所以x的系数一直是1。这样一来将\(x,y,z\)的取值代入上面的式子,我们能够得到

\[a_0+a_1+a_2+a_3=n\]

此时\(a_4,a_5,a_6,a_7\)不见了,由于\(a_i=0\),这四个待定系数的取值都是0。由此我们考虑这样一个推广:为了解出待定系数\(a_0 \cdots a_7\),我们新增一个变量\(w\),表示对一个三元组\((a_i,b_i,c_i)\)中什么都不取的方案数(\(x,y,z\)表示取其中一个的方案数),即

\[F_i=w \cdot x^0+x \cdot x^{a_i} + y \cdot x^{b_i} + z \cdot x^{c_i}\]

由于w的系数始终为1\((H_{t0}=1)\),所以\(WHT(F_i)\)中依然只有8个数:

\[x+y+z+w,x+y-z+w,x-y+z+w,x-y-z+w, \\
-x+y+z+w,-x+y-z+w,-x-y+z+w,-x-y-z+w\]

将\(w=1,x=y=z=0\)代入,我们便能够得到式子

\[a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7=[x^t]WHT(\sum{F_i})\]

并且这里可以很直观地得出\([x^t]WHT(\sum{F_i})=n\)。

再考虑设

\[F_i=w \cdot x^0+x \cdot x^{a_i} + y \cdot x^{b_i} + z \cdot x^{c_i} + u \cdot x^{a_i \oplus b_i}\]

\(WHT(F_i)\)中依然只有8个数。观察

\[H_{t(a_i \oplus b_i)}=(-1)^{count(t\ and (a_i \oplus b_i))} = (-1)^{count((t\ and\ a_i) \oplus (t\ and\ b_i)) – 2k} = (-1)^{count((t\ and\ a_i) \oplus (t\ and\ b_i))} = H_{ta_i} \cdot H_{tb_i}\]

即u的系数是x和y的系数的乘积。所以此时\(WHT(F_i)\)中的8个数为

\[x+y+z+w+u,x+y-z+w+u,x-y+z+w-u,x-y-z+w-u, \\
-x+y+z+w-u,-x+y-z+w-u,-x-y+z+w+u,-x-y-z+w+u\]

令\(u=1,x=y=z=w=0\),我们又可以得到一个新的方程:

\[a_0+a_1-a_2-a_3-a_4-a_5+a_6+a_7=[x^t]WHT(\sum{F_i})\]

同理,再加三个和\(a_i \oplus c_i,b_i \oplus c_i,a_i \oplus b_i \oplus c_i\)相关的变量,我们就可以得到我们需要的8个方程了。

另外题解里给出的做法是,先强行将所有三元组变为\((0,a_i \oplus b_i,a_i \oplus c_i)\),这样相当于只有两个变量,就只需要4个方程。这个就只贴一下代码了。


page views : 20 views

发表评论

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