P10242 [THUSC 2021] Emiya 家明天的饭

题目大意

有 \(n\) 个人和 \(m\) 种菜，第 \(i\) 个人对第 \(j\) 道菜的喜爱程度为 \(a_{i,j}\)。如果 \(a_{i,j} = -1\)则表示不喜欢。
现在你要选择一个菜的集合，你会获得喜欢集合中所有菜的人对这些菜的喜爱程度之和的权值，最大化这个权
值，\(n \leq 20,m \leq 10^6,a_{i,j} \leq 10^9\)。

分析

考虑求出 \(f_S\) 表示钦定 \(S\) 中的人喜欢所有的菜，不管其他人时，能获得的最大权值。显然答案 \(=\max_Sf_S\)。
考虑 \(a_{i,j}\) 能为哪些 \(S\) 作出贡献，设 \(t_j\) 为喜欢 \(j\) 的人的集合，那么会受到 \(a_{i,j}\) 贡献的 \(S\) 应当满足
\(S\in t_j,i\in S\)。考虑记 \(g_S\) 表示对 \(S\) 的所有子集一起造成的贡献，即 \(f_S=\sum_{S\in T}g_T\)。于是贡献就相当于
\(g_{t_j}+=a_{i,j},g_{t_j\otimes2^i}-=a_{i,j}\text{。}\)

求出 \(g\) 后再求 \(f\),直接 FWT 或 FMT 求解即可。