P2150 寿司晚宴 分析
__ryp__
·
·
个人记录
如果质因数数量非常少，比如 n \le 30，那么我们就可以直接状压，把质因数是否出现压起来。设 f(i, S, T) 表示前 i 个人，一个选了状态 j，另一个选了 k 的方案数。
很难不注意到刷表转移
\begin{aligned}
f(i, S \cup K_i, T) \gets f(i, S, T) \iff S\cup K_i \cap T = \varnothing \\
f(i, S, T \cup K_i) \gets f(i, S, T) \iff T\cup K_i \cap S = \varnothing
\end{aligned}
但是问题来了，n \le 500，我们连这玩意儿压都压不起来。
很难不注意到，一个数 x 大于 \sqrt x 的质因数最多只有一个。我们要让两个集合所选的质因数交空，实际上就是保证小因子交空的前提下，让大因子不同。
我们可以把每一个数分解，然后按大因子排序，也就是把相同的一段放在了一起。
这个大因子只有三种可能：给 S，给 T 和都不给。
设 g(i, S, T) 表示这个大因子不在 T 中的方案数，也就是可以在 S 中的方案数，那么 g 的转移是类似的；同理，我们可以算出可能在 T 中的方案数。
合并解时候，要容斥掉一个 f(i, S, T)，因为 g 和 h 都可以表示都不给的情况。
之前想过质因子状压的 idea，但是正是因为会让值域太小而没想到解决方案。这题真的不错。