异或卷积

$x^S\times x^T=x^{S\oplus T}$

$FW{T}_S(F(x))={\sum }_T(-1{)}^{|S\&T|}{F}_T(x)$

$IFW{T}_S(F(x))=\frac{1}{2^k}{\sum }_T(-1{)}^{|S\&T|}{F}_T(x)$

对吗？

---

要优化就是展开 FWT，对吗？

P5326

直接高消：$f_S={\sum }_i{f}_{S\oplus 2^i}{p}_i+1$。$f_S=\sum f_{S\oplus T}{g}_T+1$。$F(x)=F(x)G(x)+I(x)+C(x)$。

其中 $g_{2^i}=p_i$，$I_S=1$，$C_0=c$，用于调整使 $f_{\varnothing }=0$。

$FWT(F(x))(1-FWT(g(x)))=FWT(I(x))+FWT(C(x))$

在 $S=\varnothing$ 时，$FW{T}_{\varnothing }(G(x))=1$，$FW{T}_{\varnothing }(I(x))=2^n$，所以 $c=-2^n$。

在 $S=\varnothing$ 的时候，$f_{\varnothing }=IFW{T}_{\varnothing }(FWT(F(x)))=0$，所以 $FW{T}_{\varnothing }(F(x))=-{\sum }_{S\ne 0}FW{T}_S(F(x))$。

否则一个 $FW{T}_S(F(x))=\frac{-2^n}{1-FW{T}_S(G(x))}$，一个 $IFW{T}_S(F(x))=\frac{1}{2^n}({\sum }_T(-1{)}^{|S\&T|}\frac{-2^n}{2{\sum }_{j\in T}{p}_j}+\frac{2^n}{2{\sum }_{j\in T}{p}_j})$。

最后 $f_s={\sum }_T\frac{[|S\&T|\mathrm{mod}2=1]}{{\sum }_{j\in T}{p}_j}$，dp 前 $i$ 个，$\sum p_j$，与 $S$ 的交集奇偶性。复杂度 $O(n\sum p)$。

---

异或求和二元卷积

以下涉及两种元的乘法，$x^i\times x^j=x^{i\oplus j}$，$y^i\times y^j=y^{i+j}$。

CF1906K

求 $[x^0]\prod (1+2x^{a_i})$。

对每个 $S$ 求出 $[x^S]FWT(\prod (1+2x^{a_i}))$ 再 IFWT 回去。

这个等于 ${\prod }_i[x^S]FWT(1+2x^{a_i})$，即 ${\prod }_i(1+2(-1{)}^{|S\&a_i|})$。

在这里不是 $-1$ 就是 $3$，即 $(-1{)}^{n-t_S}{3}^{t_S}$，这个 $t_S$ 可以通过对 $a_i$ 的出现次数 FWT 得到。

abc367g

求 $[x^S{y}^0]\prod (1+x^{a_i}y)$，这里 $y^i\times y^j=y^{(i+j)\mathrm{mod}m}$。

$[x^S]=[y^0]\prod (1+y(-1{)}^{|S\&a_i|})$，预处理 $(\prod (1\pm y){)}^k$，复杂度 $O(nm+V\log V)$。

Q7856

求 $[x^S{y}^B]\prod (1+x^{a_i}(y^2+2y+1))$。

FWT 之后对每个 $0\le t\le n$ 求 $[y^B](1-(y^2+2y+1){)}^{n-t}(1+(y^2+2^{+}1){)}^t$。

展开式子然后 ntt 即可。

P13497

先数不可重集 $h_i,(i\le |S|)$ 的方案数，即 ${\sum }_{a\in T}[x^a{y}^i]{\prod }_{b\in S}(1+x^{b}y)$。

先 FWT，点乘，$f_s=[x^s]{\prod }_{b\in S}(1+y(-1{)}^{|s\&b|})$。

再展开一层，把所有 $f_s$ IFWT 回去，$h_i={\sum }_{a\in T}{g}_a={\sum }_{a\in T}\frac{1}{2^v}{\sum }_s{f}_s(-1{)}^{|S\&a|}$。

$h_i=[y^i]\frac{1}{2^v}{\sum }_s{\sum }_{a\in T}(-1{)}^{|s\&a|}(1+y{)}^{t{s}_s}(1-y{)}^{|S|-t{s}_s}=\frac{1}{2^v}[y^i](|T|-t{t}_s)(1+y{)}^{t{s}_s}(1-y{)}^{|S|-t{s}_s}$

$O(|S|)$ 二项式定理即可。

至于对 $2^{28}$ 的东西求 $t{s}_s={\sum }_{a\in S}[|a\&s|\mathrm{mod}2=0]$，bitset，每次加一翻转一个后缀，预处理此时对每个 $a\in S$ 的影响。

---

怎么上面写的都是求 $|a\&S|\mathrm{mod}2$ 状物。

原来标题写的是异或，那其他 FWT 咋办。

一个 or 卷积的好题。