「BZOJ2734」[HNOI2012] 集合选数

2014年11月13日3,7406

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也如此。。

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

 

说点什么

提醒
avatar
蜜の夜明け
蜜の夜明け

飘逸的思路……

Crazyxx
Crazyxx

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