NOI2015 寿司晚宴 题解

首先我们考虑一个比较基础的 $dp$。

因为数不大，所以我们可以考虑状压处理。

设 $f[S1][S2]$ 表示质数集 1 的质数状态为 $S1$，质数集 2 的质数状态为 $S2$。

状态转移方程：

$$f[j|S[i]][k]+=f[j][k]$$

$$f[j][k|S[i]]+=f[j][k]$$

注意取模。

这是比较基本的状压，复杂度是 $\mathcal O(2^{20}n)$。

考虑到一个数最多只有一个 $\geq \sqrt{n}$ 的质因数，所以单独记录这个质因数即可，其余全部不变。

于是就把复杂度优化为 $\mathcal O(2^{16}n)$。即可 AC。