[HNOI2012]集合选数

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file bzoj_2734.in Output file bzoj_2734.out

【题目描述】

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

【输入格式】

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

【输出格式】


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

【样例输入】

 
  4                        

【样例输出】

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

【提示】


【来源】

【题目来源】

耒阳大世界(衡阳八中) OJ 2734