[NOI2025] 集合 题解

去不了 NOI 的菜鸡终于把集合看懂了，写个博客加深一下印象。
[NOI2025] 集合
要求：

\[ans=\sum_P \sum_Q [f(p)=f(Q)][P\cap Q = \emptyset] \prod_{i\in P\cup Q} a_i\]
先处理这题比较特殊的 \([f(p)=f(Q)]\)，考虑枚举 \(f(P)=f(Q)=S\)。\(f(P),f(Q)\) 恰好等于 \(S\) 不好做，容斥一下变成包含：

\[\begin{aligned}ans &= \sum_S \sum_{S\subseteq T_P} \sum_{S\subseteq T_Q} \sum_{T_P \subseteq f(P)} \sum_{T_Q \subseteq f(Q)} (-1)^{|T_P|-|S|} (-1)^{|T_Q|-|S|} [P\cap Q = \emptyset] \prod_{i\in P\cup Q} a_i\\    &= \sum_S \sum_{S\subseteq T_P} \sum_{S\subseteq T_Q} \sum_{T_P \subseteq f(P)} \sum_{T_Q \subseteq f(Q)} (-1)^{|T_P|+|T_Q|-2|S|} [P\cap Q = \emptyset] \prod_{i\in P\cup Q} a_i\\\end{aligned}  \]
发现容斥系数上的 \(-2|S|\) 没有用，可以去掉，所以也就没有必要枚举 \(S\)，只需要枚举 \(T_P,T_Q\) 然后乘上合法的 \(S\) 数量即可，而合法的 \(S\) 满足 \(S\subseteq T_P,T_Q\) 也即 \(S\subseteq T_P\cap T_Q\)，所以合法的 \(S\) 数量为 \(2^{|T_P\cap T_Q|}\)。为了美观，下面用 \(S,T\) 分别代替 \(T_P,T_Q\)。

\[\begin{aligned}ans &= \sum_{S} \sum_{T} (-1)^{|S|+|T|} 2^{|S\cap T|} \sum_{S \subseteq f(P)} \sum_{T \subseteq f(Q)}  [P\cap Q = \emptyset] \prod_{i\in P\cup Q} a_i\\\end{aligned}  \]
\(S \subseteq f(P)\) 相当于什么，其实就是说 \(P\) 中的数都要是 \(S\) 的超集，我们设 \(R_S\) 为 \(S\) 的超集构成的集合，则 \(P\subseteq R_S\)，于是我们就把跟 \(f\) 有关的东西去掉了。
然后处理 \([P\cap Q = \emptyset]\)，我们直接去枚举 \(R=P\cup Q\)，显然 \(R\subseteq R_S\cup R_T\)。那么对于 \(i\in R\)，若 \(i\) 只属于 \(R_S\) 和 \(R_T\) 中的一个，则 \(i\) 只能放到那一个，否则 \(i\) 放到哪一个都可以。

\[\begin{aligned}ans &= \sum_{S} \sum_{T} (-1)^{|S|+|T|} 2^{|S\cap T|} \sum_{R\subseteq R_S\cup R_T} \prod_{i\in R} (1+[i\in R_S\cap R_T])a_i\\    &= \sum_{S} \sum_{T} (-1)^{|S|+|T|} 2^{|S\cap T|} (\prod_{i\in R_S\cup R_T \setminus R_S\cap R_T} (a_i+1)) (\prod_{i\in R_S\cap R_T} (2a_i+1))\\\end{aligned}  \]
设 \(f_S=\prod_{i\in R_S} (a_i+1),g_S=\prod_{i\in R_S} (2a_i+1)\)，这两个可以高维后缀积 \(O(n2^n)\) 预处理。又发现 \(R_S\cap R_T=R_{S\cup T}\)：

\[ans = \sum_{S} \sum_{T} (-1)^{|S|+|T|} 2^{|S\cap T|} f(S)f(T)\dfrac{g(S\cup T)}{f(S\cup T)^2}\]
然后这里有个问题是分母可能为 \(0\)，有一个 trick 是直接把每个数用 \(x\times 0^k\) 的形式存储，表示这个数里面目前有 \(k\) 个 \(0\)，然后就可以做除法了。
发现这个式子里同时有 \(S\cap T\) 和 \(S\cup T\)，但是 \(S\cap T\) 我们只关心他的大小，所以我们可以用 \(|S\cap T|=|S|+|T|-|S\cup T|\) 来换掉：

\[\begin{aligned}ans &= \sum_{S} \sum_{T} (-1)^{|S|+|T|} 2^{|S|+|T|-|S\cup T|} f(S)f(T)\dfrac{g(S\cup T)}{f(S\cup T)^2} \\&= \sum_{S} \sum_{T} (-2)^{|S|}f(S) \times (-2)^{|T|}f(T) \times  \dfrac{g(S\cup T)}{2^{|S\cup T|}f(S\cup T)^2}\end{aligned}  \]
设 \(F(S)=(-2)^{|S|}f(S),h=F\times F\)，这里 \(\times\) 是或卷积，则：

\[ans=\sum_S \dfrac{h(S)g(S)}{2^{|S|}f(S)^2}\]
最后一个问题是，这里 \(F\) 是用 \(x\times 0^k\) 的形式存储，但是做 FMT 的时候涉及到加减法，当 \(k_1\ne k_2\) 时，两个数 \(x1\times 0^{k_1},x2\times 0^{k_2}\) 无法简单的加减法。
不过注意到我们在除以 \(f(S)^2\) 之后不可能除出来一个 \(0\) 的负次幂，所以对于分子中 \(0\) 的非最低次项他除完分母之后 \(0\) 的幂一定 \(>0\)，所以贡献一定为 \(0\)，因此在做加减法的时候直接舍弃次幂大的那个即可。
code
[code]#include#define Debug puts("-------------------------")using namespace std;const int N=(1=1,a=1ll*a*a%mod;        }        return ans;}struct Val{        int x,k;        Val() : x(0),k(0) {}        Val(int _x,int _k) : x(_x),k(_k) {}}f[N],g[N],h[N],F[N]; Val operator * (const Val &u,const Val &v){return Val(1ll*u.x*v.x%mod,u.k+v.k);}Val operator + (const Val &u,const Val &v){        if(u.k==v.k) return Val((u.x+v.x)%mod,u.k);        return u.k