首页 > 代码库 > bzoj2734【HNOI2012】集合选数
bzoj2734【HNOI2012】集合选数
2734: [HNOI2012]集合选数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
search=day2" style="color:blue; text-decoration:none">day2
状压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; }
bzoj2734【HNOI2012】集合选数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。