《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。
| 题目名称 | 1344. [HNOI 2012]集合选数 |
|---|---|
| 输入输出 | bzoj_2734.in/out |
| 难度等级 | ★★ |
| 时间限制 | 10000 ms (10 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 QhelDIV
于2013-04-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：41， 提交：159， 通过率：25.79% | ||||
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 Heaven |
100 | 0.004 s | 0.81 MiB | C++ |
|
Youngsc |
100 | 0.005 s | 0.00 MiB | C++ |
 Enterprise |
100 | 0.016 s | 8.79 MiB | C++ |
 小一米 |
100 | 0.018 s | 0.45 MiB | C++ |
|
小一米 |
100 | 0.021 s | 0.45 MiB | C++ |
 vampire |
100 | 0.023 s | 72.37 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.027 s | 16.43 MiB | C++ |
 wumingshi |
100 | 0.042 s | 2.31 MiB | C++ |
 haah |
100 | 0.058 s | 0.57 MiB | C++ |
| 关于 集合选数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
调试的时候发现bool数组中除了有true和false还出现了2。。。后来在大神的教导下发现是数组开小了。。。
| ||||
|
怎么就矩阵了，难道不是对每个弱联通块dp一下吗？
 FoolMike
2017-10-13 15:04
5楼
| ||||
|
花间一壶酒
 A_LEAF
2017-05-25 10:19
4楼
| ||||
|
回复 @HZOI_star* :
MMP  君莫笑
2017-05-25 09:34
3楼
| ||||
|
矩阵真神奇
  Hzoi_Mafia
2017-05-24 16:29
2楼
| ||||
|
神奇的构思矩阵。。。
 GDFRWMY
2014-02-01 11:18
1楼
| ||||
【题目描述】
【输入格式】
只有一行，其中有一个正整数 n，30%的数据满足 n≤20。
【输出格式】
仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件 的子集。
【样例输入】
4
【样例输出】
8
【样例解释】
有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
【提示】