【BZOJ2734】【HNOI2012】集合选数

首先如果两个数除掉所有\(2\)和\(3\)的因子得到的数\(p\)相同它们才可能有约束关系,所以有约束关系的数是在一个个互不相交的集合中

那么我们可以先按照\(p\)分出集合,对于任意一个集合我们可以将里面的数可以按照倍数关系排列成矩阵的形式

$$
\begin{matrix}
p&3p&9p&…&\\
2p&6p&18p&…&\\
4p&12p&36p&…&\\
…&…&…&…\\
\end{matrix}
$$

其中相邻的数是不能同时选择的。

注意到列数不大于\(\lceil log_{3}n\rceil=11\),那么直接状压dp求出每个集合中选数的方案。最后乘起来就是答案。

说点什么

您将是第一位评论人!

提醒
wpDiscuz