P13275

写出答案式子：

对 $[f(P)=f(Q)]$ 限制进行容斥：即对于每一位 $x$ 应有 $[x\in f(P)]=[x\in f(Q)]$ 成立，记 $P_x=[x\in f(P)],Q_x=[x\in f(Q)]$，

则：

其中倒数第二步为枚举 $S=B\cup A,T=C\cup A$。从而答案为：

考察 $P,Q$ 可以取到的集合：$P,Q$ 分别为所有是 $S,T$ 超集的数构成集合（分别记为 $A_S,A_T$）的子集；枚举 $R=P\cup Q\subseteq A_S\cup A_T$，则对于 $i\in R$，若 $i\in A_S\cap A_T$ 则可将 $i$ 任意分配 $P/Q$ 否则 $i$ 属于 $P/Q$ 是确定的，即答案为：

令 $f_S=\prod\limits_{S\subseteq T} (a_T+1),g_S=\prod\limits_{S\subseteq T} (2a_T+1)$，则答案为：

$f_S$ 和 $g_S$ 均可以高维后缀积计算，复杂度 $\mathcal{O}(n2^n)$，则此时暴力算上面的式子就可以得到一个 $\mathcal{O}(4^n)$ 的做法；然而存在问题：会出现 $/0$ 的情况。处理很简单：记录 $f_S,g_S=a\cdot0^k$ 即可，乘除均有良定义。

注意到 $|S\cap T|+|S\cup T|=|S|+|T|$，将答案按 $S/T/S\cup T$ 整理得：

令 $\hat{f}_S=(-2)^{|S|}f_S$，得 $h=\hat{f}\times \hat{f}$，则答案为：（此处乘法是 or 卷积）

复杂度 $\mathcal{O}(n2^n)$。

仍然存在问题：$\hat{f}$ 与 $f$ 一样是 $a\cdot 0^k$ 形式保存，而 $a_1\cdot 0^{k_1}$ 和 $a_2\cdot 0^{k_2}$ 加减法若 $k_1\ne k_2$ 是没有良定义的（除非维护关于 $0$ 的多项式），但是发现最终非最低位在除以 $f_S^2$ 后 $0$ 的次数必然 $>0$，从而可以直接舍去，即保留 $0$ 次数较低的项即可。