集合选数 题目背景： bzoj2734 分析：构造 + 状态压缩DP 表示思路比较清奇啊·····我是没有想到的······我们来考虑如何选择可行的数字，先构造一个矩阵 1 3 9 27 81 2432 6 18 54 162 4864 12 36 108 324 9728 24 72 216 648 19

Description 《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取