CF1336E2
lsj2009
·
·
题解
记：
F_{\mathcal{B}}(x)=\sum\limits_{u\in \operatorname{span}(\mathcal{B})} x^u\\
G_{\mathcal{B}}(x)=\sum\limits_{u\in \operatorname{span}(\mathcal{B})} x^{\operatorname{popcount}(u)}
若 \mathcal{B}_0 为序列 a_{1\sim n} 的一组基，则一个结论是答案生成函数等于 G_{\mathcal{B}_0}(x)2^{n-\operatorname{rank}(\mathcal{B}_0)}，暴力枚举复杂度 \mathcal{O}\left(2^{\operatorname{rank}(\mathcal{B}_0)}\right)。
进一步刻画：（H_k(x)=\sum\limits_{\operatorname{popcount}(u)=k}x^u）
\begin{aligned}
[x^k]G_{\mathcal{B}_0}
&=[x^0]\left(F_{\mathcal{B}_0}\times H_k\right)\\
&=[x^0]\operatorname{IFWT}\left(
\operatorname{FWT}(F_{\mathcal{B}_0})\cdot
\operatorname{FWT}(H_k)\right)\\
&=
2^{-m}\sum[x^u]\operatorname{FWT}(F_{\mathcal{B}_0})\times [x^u]
\operatorname{FWT}(H_k)\\
\end{aligned}
根据我们之后的讨论，可以得到结论：\operatorname{FWT}(F_{\mathcal{B}_0}) 内非零项不超过 2^{m-\operatorname{rank}(\mathcal{B}_0)} 个，但对于每个 k 都枚举这些项再和 \operatorname{FWT}(H_k) 对应位相乘复杂度要多一个 m；但注意到 [x^u]\operatorname{FWT}(H_k) 仅和 \operatorname{popcount}(u),k 有关，如此可以事先将 \operatorname{FWT}(F_{\mathcal{B}_0}) 变换成 G 的形式，再计算答案显然是 poly 的。
如此我们仅需求出 \operatorname{FWT}(F_{\mathcal{B}_0})。
\begin{aligned}
[x^u]\operatorname{FWT}(F_{\mathcal{B_0}})&=
\prod\limits_{v\in\mathcal{B}_0}[x^u]\operatorname{FWT}(1+x^v)\\
&=\prod\limits_{v\in\mathcal{B}_0}\left(1+(-1)^{\operatorname{popcount}(u\cap v)}\right)\\
&=2^{\operatorname{rank}(\mathcal{B}_0)}
[\forall v\in\mathcal{B_0},\operatorname{popcount}(u\cap v)\equiv0\pmod{2}]
\end{aligned}
考察所有满足艾弗森内限制的向量。该限制可以刻画为 \operatorname{rank}(\mathcal{B}_0) 个方程且互相线性无关，则解构成一个 m-\operatorname{rank}(\mathcal{B}_0) 维线性空间；找出基底 \mathcal{B}_1 满足 \forall x\in\mathcal{B}_0,y\in\mathcal{B}_1 满足 \operatorname{popcount}(x\cap y)\equiv 0\pmod{2} 且 \operatorname{rank}(\mathcal{B}_1)=m-\operatorname{rank}(\mathcal{B}_0)，则有 \operatorname{FWT}(F_{\mathcal{B_0}})=2^{\operatorname{rank}(\mathcal{B}_0)}F_{\mathcal{B_1}}(x)。
接下来我们直接给出 \mathcal{B}_1 的构造：
即先将 \mathcal{B}_0 消成主元列仅有一个 1（为了配合上图理解可以将位置换使得主元位都在高位），然后将 \mathcal{B}_1 依次在其余位每列放一个 1，高位设为 \mathcal{B}_0 低位矩阵的转置。容易 check 其满足条件：由于 \mathcal{B}_0 每个向量在高位仅有一个 1，\mathcal{B_1} 低位也仅有一个 1，故 \operatorname{popcount}(x\cap y) 至多为 2，且对于两个主元的位分别作为左上/右下角的矩阵可以发现其关于主对角线对称，即两个主元位必然同时为 0/1。
将两个做法阈值分治，复杂度 \mathcal{O}\left(2^{m/2}+\operatorname{poly}(m)\right)。