【UNR #2】黎明前的巧克力
难度：简单
考虑如果一个集合大小为 $|S|$ 的集合 $S$ 中的所有数字异或和为 $0$，那对答案的贡献应该是 $2^{|S|}$，前提是 $|S|\not =0$，如果 $|S|=0$，则贡献应该是 $0$，我们最后再去掉这个限制的影响。
由此我们可以写出巧克力的结合幂级数：
$$
1+2x^{a_i}
$$
一个暴力的想法是直接用 $FWT$，但是这样一共要做 $n$ 次 $FWT$，每一次都是 $O(v\log v)$ 的（$v$ 表示值域），对于时间来说非常浪费，我们需要考虑利用这个集合幂级数的特殊性质。
根据我们之前博客讲过的 $FWT(A)_i$ 的式子，容易发现，每一项的数都是 $-1$ 或者是 $3$，所以我们可以考虑算出来最后的每个位置上有多少个集合幂级数是 $-1$，有多少个是 $3$。具体来说，把上面的集合幂级数累加，然后只做一遍 $FWT$，通过解方程，我们可以得到把上面的式子异或卷积之后的到的 $FWT$ 式子。然后 $IFWT$ 即可。
代码：
1 |
|
CF1119H
难度：较难
可以转化成上面那道题。
第一个转化：容易发现这个题的集合幂级数是这个形式：
$$
ux^{a_i}+vx^{b_i}+wx^{c_i}
$$
如果直接考虑的话，情况个数是 $2^3=8$，我们可以用下面的集合幂级数代替上面的，以把情况数缩小 $\frac{1}{2}$：
$$
ux^{a_i\oplus c_i}+vx^{b_i\oplus c_i}+w
$$
这样做对答案有什么影响，不难发现，我们只需要让答案下标异或上 $\oplus_{i=1}^{n}c_i=xsum$，就可以修正这样做带来的影响。这种技巧在没有常数项的时候适用，如果有常数项的存在将无法缩小情况。
接下来我们考虑转化成上面那道题解方程式的模型。不考虑 $w$，一共有 $4$ 种情况：
$$
\begin{cases}
u+v\
u-v\
-u+v\
-u-v\
\end{cases}
$$
设 $4$ 种情况在第 $i$ 位的出现次数分别为 $A_i,B_i,C_i,D_i$。
那么这一位的 $FWT$ 值应该是 $(u+v)^{A_i}(u-v)^{B_i}(-u+v)^{C_i}(-u-v)^{D_i}$，考虑通过解方程得到 $A_i,B_i,C_i,D_i$ 是多少。
显然 $A_i+B_i+C_i+D_i=n$，通过计算 $FWT(\sum x^{a_i\oplus c_i})$ 可以得到 $A_i+B_i$ 是多少（通过解一个二元方程）。同理通过计算 $FWT(\sum x^{b_i\oplus c_i})$ 可以得到 $A_i+C_i$ 是多少。
非常人类智慧的一点是我们可以通过计算 $FWT(\sum x^{(a_i\oplus c_i)\oplus (b_i \oplus c_i)})$ 来得到 $A_i+D_i$，这是因为以下式子成立：
由
$$
FWT(x^{(a_i\oplus c_i)\oplus (b_i \oplus c_i)})=FWT(x^{a_i\oplus b_i})
$$
可知
$$
[x^k]=(-1)^{|k&(a_i\oplus b_i)|}=(-1)^{(k&a_i)\oplus (k&b_i)}=(-1)^{k&a_i}(-1)^{k&b_i}
$$
所以只有当两边同号的时候 $x^k$ 的系数才能是 $1$，由此通过解方程我们可以得到 $A_i+D_i$。
代码：
1 |
|
出现的问题：取模混乱，如果取模太过于复杂一定要记得 ll；记得处理负数。
石家庄的工人阶级队伍比较坚强
因为不会卡常，所以只得了 $85pts$，是一道 k 进制 FWT 模板题，只需要一定的转化。不难发现 $u$ 是 $x-y$ 三进制下 $1$ 的个数，而 $v$ 三进制下 $2$ 的个数，当然这里的 $-$ 是在三进制下的。所以整个 $b$ 就和 $x-y$ 相关了，卷积即可。
代码：
1 |
|