【bzoj2734】[HNOI2012]集合选数

2014年11月13日3,0665

Description

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

Input

 只有一行,其中有一个正整数 n,30%的数据满足 n≤20。

Output

 仅包含一个正整数,表示{1, 2,…, n}有多少个满足上述约束条件 的子集。

Sample Input

4

Sample Output

8
【样例解释】
有8 个集合满足要求,分别是空集,{1},{1,4},{2},{2,3},{3},{3,4},{4}。

题解

写出如下矩阵

1 3  9  27…

2 6 18 54…

4 12 36 108…

发现最多有11列。。。

我们在其中选取一些数,相邻的不能选择

然后就可以状压求方案数了,但是5没有出现,同样5的倍数也没有出现,7也如此。。

应该记录哪些数字出现过,没出现过就作为矩阵的第一个元素,最后把若干个矩阵的方案相乘

 

  • Crazyxx2015年3月1日 下午7:44 回复

    您如何分析此题的复杂度?

    #1  
    • hzwer2015年3月1日 下午8:34 回复
      admin

      不会啊。。。

      #11
      • 黄学长的小号2015年3月4日 下午5:10 回复

        黄学长又装弱了,因为这是按照整除关系构建的三角形图,所以三角形并不高,最坏的情况是第一行是1,最后第k行是2^k,深度是O(logn)的,每一行的元素最多也是O(logn)的,一个元素推到下一行的状态是O(2^k)的,越深枚举次数越多,但点数也越少,可以考虑对每个三角形图进行分析,一个很难达到的上界时间复杂度是O(nlogn)。

        #12
        • Crazyxx2015年3月5日 上午10:36 回复

          Orz

          #13
  • 蜜の夜明け2016年3月16日 下午9:17 回复

    飘逸的思路……

    #2