标签：end 题解 FMT sum FWT mathcal prod align

CF449D Jzzhu and Numbers

简要题意

给定序列 \(\{a_n\}\)，求有多少个子序列满足所有元素的按位与为 \(0\)。

题解

F1

考虑 FWT 的与卷积形式，构造序列 \(\{A_n\}\)，使 \(A_i=\displaystyle\sum_{j\&i=i}a_i\)，记 \(B_i=\displaystyle\sum_{b\in a}[(b_1\&b_2\&\cdots\&b_n)\&i=i]\)，则有 \(B_i=2^{A_i}-1\)，最后对 \(B_i\) 做一次 IFWT 或者容斥即可。

F2

考虑一个背包 \(f_{i,j}\) 表示考虑 \(a_1\) 到 \(a_i\)，按位与结果为 \(j\) 的子序列数量。
有转移：

\[f_{i,j}=\sum_{k\&a_i=j}f_{i-1,k}+f_{i-1,j} \]

两端做 FWT：

\[\begin{align*} F_{i,j}&=\mathcal{F}(\sum_{k\&a_i=j}f_{i-1,k})+F_{i-1,j}\\ &=F_{i-1,j}G_{i-1,j}+F_{i-1,j}\\ &=F_{i-1,j}(G_{i-1,j}+1)\\ \end{align*} \]

其中 \(F_{i,\cdot}\) 是 \(f_{i,\cdot}\) 的 FWT，\(G_{i,\cdot}\) 是 \(g_{i,\cdot}\) 的 FWT，\(g_{i,j}=\begin{cases}1 & j=a_i\\0 & j\ne a_i\end{cases}\)。

简单计算可以得到同 F1 的结果，有 \(F_{n,\cdot}=A\)。

record

CF1119H Triple

简要题意

给定几个数：\(n,t,u,v,w\) 满足 值域 \(≤2^t\)。给出 \(n\) 个三元组 \((ai,bi,ci)\)，表示有 \(x\) 个 \(a_i\)​，\(y\) 个 \(b_i\)​，\(z\) 个 \(c_i\)​。对于每个 \(k\in[0,2t−1]\)，请求出从每组选出一个数的异或和为 \(k\) 的方案数。

题解

我们要求

\[ans=\prod ux^{a_i}+vx^{b_i}+wx^{c_i} \]

其中 \(\prod\) 为异或卷积。考虑进行 FWT，有

\[\begin{align*} \mathcal{F}(ans)&=\mathcal{F}(\prod ux^{a_i}+vx^{b_i}+wx^{c_i})\\ &=\prod\mathcal{F}(ux^{a_i}+vx^{b_i}+wx^{c_i})\\ &=\prod u\mathcal{F}(x^{a_i})+v\mathcal{F}(x^{b_i})+w\mathcal{F}(x^{c_i}) \end{align*} \]

第二行之后及下文的 \(\prod\) 为点积。
注意到 \(\mathcal{F}(x^k)=\sum_S(\pm1)x^S\)，因此

\[[x^k]\mathcal{F}(ans)=\prod(\pm u\pm v\pm w) \]

总共只有八种情况，对于每一个 \(k\)，算出这八种情况在乘积中各出现多少次，然后快速幂就做完了。

考虑到八种情况还是太臃肿了，我们进行一个小 trick：将 \(b_i,c_i\) 异或上 \(a_i\)，然后令 \(a_i=0\)，最终输出答案的时候再异或回来即可，故 \(\mathcal{F}(x^{a_i})=\mathcal{F}(x^\varnothing)=\sum x^S\)，所以 \(u\) 的系数恒为 \(1\)，只剩下四种情况

\[u+v+w,u-v+w,u+v-w,u-v-w \]

记他们出现的次数分别为

\[c_1,c_2,c_3,c_4 \]

接下来考虑如何计算。直接算显然是不切实际的，但是我们考虑只计算 \(v\) 的系数的和 \(p_v\)，则有对于最终答案的 \(x^k\) 这一项，

\[\begin{align*} p_v&=\sum[x^k]\mathcal{F}(x^{b_i})\\ &=[x^k]\sum\mathcal{F}(x^{b_i})\\ &=[x^k]\mathcal{F}(\sum x^{b_i}) \end{align*} \]

对于 \(w\) 和 \(p_w\) 同理，再加上 \(c_1+c_2+c_3+c_4=n\)，我们得到了三个线性无关的方程，考虑再找一个方程：
注意到 \(\mathcal{F}(x^{b_i})\mathcal{F}(x^{c_i})=\mathcal{F}(x^{b_i\oplus c_i})\) 为 \(v,w\) 系数的乘积记为 \(p_{v\oplus w}\)，有

\[\begin{align*} p_{v\oplus w}&=[x^k]\mathcal{F}(\sum x^{b_i\oplus c_i}) \end{align*} \]

至此四个方程集齐：

\[\begin{align*} &c_1+c_2+c_3+c_4=n\\ &c_1-c_2+c_3-c_4=p_v\\ &c_1+c_2-c_3-c_4=p_w\\ &c_1-c_2-c_3+c_4=p_{v\oplus w} \end{align*} \]

解出来之后做个快速幂，然后 IFWT 就做完了。

record

标签：end,题解,FMT,sum,FWT,mathcal,prod,align
From： https://www.cnblogs.com/watware-cym/p/17287681.html