P13275
lsj2009
·
·
题解
写出答案式子：
\sum\limits_P \sum\limits_Q [f(P)=f(Q)][P\cap Q=\emptyset]\prod\limits_{i\in P\cup Q} a_i
对 [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)]，
则：
\begin{aligned}
[f(P)=f(Q)] & = \prod\limits_{0\le i<n} [P_i=Q_i]\\
& = \prod\limits_{0\le i<n} ((P_i\wedge Q_i)+(\neg P_i\wedge\neg Q_i))\\
& = \prod\limits_{0\le i<n} (1-(\neg P_i\wedge Q_i)-(P_i\wedge\neg Q_i))\\
& = \prod\limits_{0\le i<n} (1-(Q_i-P_i\wedge Q_i)-(P_i-P_i\wedge Q_i))\\
& = \prod\limits_{0\le i<n} (2P_i\wedge Q_i-P_i-Q_i+1)\\
& = \sum\limits_{A\subseteq f(P)\cap f(Q)}\sum\limits_{B\subseteq f(P),A\cap B=\emptyset}
\sum\limits_{C\subseteq f(Q),A\cap C=\emptyset,B\cap C=\emptyset} 2^{|A|}(-1)^{|B|+|C|}\\
& = \sum\limits_{S\subseteq f(P)} \sum\limits_{T\subseteq f(Q)} 2^{|S\cap T|}(-1)^{(|S|-|S\cap T|)+(|T|-|S\cap T|)}\\
& = \sum\limits_{S\subseteq f(P)} \sum\limits_{T\subseteq f(Q)} 2^{|S\cap T|}(-1)^{|S|+|T|}
\end{aligned}
其中倒数第二步为枚举 S=B\cup A,T=C\cup A。从而答案为：
\begin{aligned}
& \sum\limits_P\sum\limits_Q[P\cap Q=\emptyset]\sum\limits_{S\subseteq f(P)}\sum\limits_{T\subseteq f(Q)}(-1)^{|S|+|T|}2^{||S\cap T|}\prod\limits_{i\in P\cup Q} a_i\\
= & \sum\limits_S\sum\limits_T(-1)^{|S|+|T|}2^{|S\cap T|}\sum\limits_{S\subseteq f(P)}\sum\limits_{T\subseteq f(Q)}[P\cap Q=\emptyset]\prod\limits_{i\in P\cup Q} a_i
\end{aligned}
考察 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 是确定的，即答案为：
\begin{aligned}
& \sum\limits_S\sum\limits_T(-1)^{|S|+|T|}2^{|S\cap T|}
\sum\limits_{R\subseteq A_S\cup A_T}\prod\limits_{i\in R} (1+[i\in A_S\cap A_T])a_i\\
= & \sum\limits_S\sum\limits_T(-1)^{|S|+|T|}2^{|S\cap T|}
\left(\sum\limits_{R_1\subseteq A_S\cap A_T} \prod\limits_{i\in R_1} 2a_i\right)
\left(\sum\limits_{R_2\subseteq A_S\cup A_T\setminus(A_S\cap A_T)} \prod\limits_{i\in R_2} a_i\right)\\
= & \sum\limits_S\sum\limits_T(-1)^{|S|+|T|}2^{|S\cap T|}
\left(\prod\limits_{i\subseteq A_S\cap A_T} (2a_i+1)\right)
\left(\prod\limits_{i\subseteq A_S\cup A_T\setminus(A_S\cap A_T)} (a_i+1)\right)
\end{aligned}
令 f_S=\prod\limits_{S\subseteq T} (a_T+1),g_S=\prod\limits_{S\subseteq T} (2a_T+1)，则答案为：
\sum\limits_S\sum\limits_T(-1)^{|S|+|T|}2^{|S\cap T|}f_Sf_T\frac{g_{S\cup T}}{(f_{S\cup T})^2}
注意到 $|S\cap T|+|S\cup T|=|S|+|T|$，将答案按 $S/T/S\cup T$ 整理得：
$$
\sum\limits_S\sum\limits_T\left((-2)^{|S|}f_S\right)\left((-2)^{|T|}f_T\right)\frac{g_{S\cup T}}{(f_{S\cup T})^22^{|S\cup T|}}
$$
令 $\hat{f}_S=(-2)^{|S|}f_S$，得 $h=\hat{f}\times \hat{f}$，则答案为：（此处乘法是 or 卷积）
$$
\sum\limits_S h_S\frac{g_S}{f_S^22^{|S|}}
$$
复杂度 $\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$ 次数较低的项即可。