bzoj2734【HNOI2012】集合选数
2024-08-31 12:50:00
2734: [HNOI2012]集合选数
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 831 Solved: 487
[Submit][Status][Discuss]
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}。
【例子解释】
有8 个集合满足要求,各自是空集,{1},{1。4}。{2}。{2,3},{3}。{3,4},{4}。
HINT
Source
状压DP思路好题
写出这样一个矩阵
1 3 9 27 …
2 6 18 54 …
4 12 36 108 …
…
能够发现最多有12行。
这样我们仅仅要枚举左上角的数x,就能够得到一个不同的矩阵。对于每个矩阵须要选一些数,但不能选相邻的数,状压DP解决。
对于每个矩阵,把方案数相乘即为答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
#define mod 1000000001
using namespace std;
int n;
ll ans=1,f[20][4100],num[20];
bool vst[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll calc(int x)
{
int cnt=0;
memset(num,0,sizeof(num));
memset(f,0,sizeof(f));
f[0][0]=1;
while (x<=n)
{
cnt++;
int tmp=x;
while (tmp<=n)
{
num[cnt]++;
vst[tmp]=true;
tmp*=3;
}
F(i,0,(1<<num[cnt])-1)
{
int p;
for(p=1;p<num[cnt];p++) if ((i&(1<<(p-1)))&&(i&(1<<p))) break;
if (p!=num[cnt]) continue;
F(j,0,(1<<num[cnt-1])-1) if (!(i&j)) (f[cnt][i]+=f[cnt-1][j])%=mod;
}
x*=2;
}
ll t=0;
F(i,0,(1<<num[cnt])-1) (t+=f[cnt][i])%=mod;
return t;
}
int main()
{
memset(vst,false,sizeof(vst));
n=read();
F(i,1,n) if (!vst[i]) (ans*=calc(i))%=mod;
printf("%lld\n",ans);
return 0;
}
最新文章
- 基于.NET平台常用的框架整理(转)
- js数组与对象性能比较
- .NET 4.5 中新提供的压缩类
- nginx 目录文件列表功能配置
- ChatRichTextBox : RichTextBox
- PRML读书会第十三章 Sequential Data(Hidden Markov Models,HMM)
- SSL/TLS 高强度加密: 常见问题解答
- Python 前端之JS
- NYOJ-456 邮票分你一半 AC 分类: NYOJ 2014-01-02 14:33 152人阅读 评论(0) 收藏
- cxf的使用及安全校验-02创建简单的客户端接口
- hdu 4502 吉哥系列故事——临时工计划_简单dp
- svn中的Trunk,branches,tags深度理解
- Java多线程的wait(),notify(),notifyAll()
- AFNetWorking POST Multi-Part Request 上传图片
- 《算法导论》习题2.3-5 二分搜索 Binary Search
- Find modern, interactive web-based charts for R at the htmlwidgets gallery
- IPV6与IPV4的区别
- spark on yarn 运行问题记录
- Even Parity UVA - 11464 (枚举)
- __x__(11)0906第三天__图片标签
热门文章
- 基于Linux环境Tomcat-MySQL的server搭建
- ”危险“的RESTRICT与GCC的编译优化(编程者对编译器所做的一个“承诺”:使用restrict修饰过的指针,它所指向的内容只能经由该指针修改)
- mysqli数据库操作简单实例
- 3. Longest Substring Without Repeating Character[M] 最大不重复子串
- Ubuntu16.04下沙盒数据导入到 Neo4j 数据库(图文详解)
- UWP 开发相关
- JSON是什么?为JavaScript准备的数据格式
- [oracle] 组织架构退格显示 connect by
- Windows 错误 0x80070570
- js类的使用