题出的好！难度适中，覆盖知识点广，题目有着切合实际的背景，解法比较自然。给出题人点赞 ！

· · 题解

题目出的非常好，他好就好在他哪里都好，如果能换道题出的话，那想必一定会更好。

注意到题目中比较复杂的限制是 f(P)=f(Q)，考虑对这一条限制直接拆位做，记 f 表示一个 n 位的原问题，由于 f(P)=f(Q)，则有 f=g^{11}+g^{00}。其中 g^{ij} 表示一个 n-1 位的问题，其中 f(P) 在第 n 位要求为 i，f(Q) 在第 n 位要求为 j。但你注意到要求为 0 这一限制并不好达到。考虑容斥为要求为 1 和无限制。也即 g^{11}=h^{++},g^{00}=h^{--}-h^{+-}-h^{-+}+h^{++}，也即 f=h^{--}-h^{-+}-h^{+-}+2h^{++}。

换而言之，f=\sum\limits_{P,Q}w(P,Q)\times t(P,Q)，其中 w(P,Q) 表示容斥系数，每一位形如 \begin{bmatrix}1&-1\\-1&2\end{bmatrix}。而 t(P,Q) 表示贡献式子，对于每一个 S，其可以在 P 里当且仅当其为 P 的超集，Q 同理。故有 t(P,Q)=f_P\times f_Q\times g_{P\cup Q}，（由于下文中不再使用原来的 f 和 g，我们重标号一下）其中 f_S 表示 S 超集的 \prod(a_i+1)，g_S 表示 \prod\dfrac{2a_i+1}{(a_i+1)^2}。

我们在 P\cup Q 处统计答案，对 w(P,Q) 构造 FWT 矩阵 \begin{bmatrix}1&0\\1&-2\end{bmatrix} 和 IFWT 矩阵 \begin{bmatrix}1&0\\-\frac{1}{2}&\frac{1}{2}\end{bmatrix}。在特殊性质 B 下可以做到 \Omicron(2^n\times n)。

无特殊性质时需记录 0 的次数，然而该多项式会有 \Omicron(2^n) 次，复杂度退化到 \Omicron(4^n\times n)。根据某些经典模型，过程中多项式次数不降，而我们只需求最低次项系数，因此只需记录最低次项系数即可。时间复杂度 \Omicron(2^n\times n)。