A2292 | 集合选数
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n \le 10^5$，如何求出 $\{1,2,\ldots ,n\}$ 的满足上述约束条件的子集的个数（只需输出对 $10^9+1$ 取模的结果），现在这个问题就交给你了。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n \le 10^5$，如何求出 $\{1,2,\ldots ,n\}$ 的满足上述约束条件的子集的个数（只需输出对 $10^9+1$ 取模的结果），现在这个问题就交给你了。
输入格式
只有一行，其中有一个正整数 $n$。$30 \%$ 的数据满足 $n \le 20$。
输出格式
仅包含一个正整数，表示 $\{1,2,\ldots ,n\}$ 有多少个满足上述约束条件的子集。
输入输出样例
输入 #1
4
输出 #1
8
**【样例解释】**
有 $8$ 个集合满足要求，分别是空集，${1}$，$\{1,4\}$，$\{2\}$，$\{2,3\}$，$\{3\}$，$\{3,4\}$，$\{4\}$。
**【数据范围】**
对于 $30 \%$ 的数据，$n \le 20$。
对于 $100 \%$ 的数据，$1 \le n \le 10^5$。
有 $8$ 个集合满足要求，分别是空集，${1}$，$\{1,4\}$，$\{2\}$，$\{2,3\}$，$\{3\}$，$\{3,4\}$，$\{4\}$。
**【数据范围】**
对于 $30 \%$ 的数据，$n \le 20$。
对于 $100 \%$ 的数据，$1 \le n \le 10^5$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted