CF449D Jzzhu and Numbers

有一个很蠢但是很好写的做法。

就是你先令 \(t_i\) 为与起来恰好为 \(i\) 的方案数，然后 \(g_i\) 为与起来子集中有 \(i\) 的方案数。

然后 \(g_S=\sum\limits_{T\subseteq S}t_T\)，反演一下变成 \(t_{S}=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}g_{T}\)。注意到可以 \(O(w)\) 枚举 \(T\)。

现在考虑如何求 \(g_T\)。显然与起来包含 \(T\) 意味着所选数都包含 \(T\)，令 \(f_{S}=\sum\limits_{S\subseteq T}c_{T}\)，\(c_T\) 为 \(a\) 中 \(T\) 的出现次数，那么显然有 \(g_T=2^{f_{T}}-1\)。

然后 \(f_{T}\) 显然就是一个超集和，取反后变成子集和，FWT 即可。

复杂度 \(O(n+w\log w)\)，不用什么麻烦的特判。