TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4771
  • 题目
  • P4771集合选数
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    《集合论与图论》这门课程有一道作业题,要求同学们求出{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}。


    来源  hnoi2012 集合选数