首页 > 代码库 > 【BZOJ-2732】集合选数 状压DP （思路题）
【BZOJ-2732】集合选数 状压DP （思路题）
2734: [HNOI2012]集合选数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1070 Solved: 623
[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
day2
Solution
一开始真没想到..
就是写一个矩阵
$$\begin{bmatrix}x & 3x& 9x& ...&\\ 2x & 6x& 18x& ...&\\ 4x& 12x& 36x& ...&\\ ...& ...& ...& ...& \end{bmatrix}$$
然后我们发现实际上就是需要求矩阵中，不允许出现相邻的两个数。
因为这个矩阵的列数是$log_{3}$，行数是$log_{2}$的，显然可以状压..
但是有些数并不会出现在这个矩阵中，所以构造完一个后，找下一个没出现过的x重新构造，乘法原理结合起来即可。
Code
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define LL long longinline 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;}#define MAXN 100010#define P 1000000001int a[21][21],N,M,end[21];LL f[21][2049],bin[21],ANS=1;bool visit[MAXN];inline void Pre(int x){ memset(a,0,sizeof(a)); memset(end,0,sizeof(end)); end[0]=1; a[1][1]=x; for (int i=2; ; i++) if ((a[i-1][1]<<1)<=N) a[i][1]=a[i-1][1]<<1; else {M=i-1; break;} for (int i=1; i<=M; i++) for (int j=2; ; j++) if (a[i][j-1]*3<=N) a[i][j]=a[i][j-1]*3; else {end[i]=j-1; break;}// puts("======================================");// for (int i=1; i<=M; i++,puts(""))// for (int j=1; a[i][j]; j++)// printf("%d ",a[i][j]);// puts("======================================"); for (int i=1; i<=M; i++) for (int j=1; j<=end[i]; j++) visit[a[i][j]]=1;// for (int i=1; i<=M; i++) printf("%d ",end[i]); puts("");}inline LL DP(int x){ Pre(x); memset(f,0,sizeof(f)); f[0][0]=1; for (int i=0; i<=M; i++) for (int j=0; j<bin[end[i]]; j++) if (f[i][j]) for (int k=0; k<bin[end[i+1]]; k++) (f[i+1][k]=(!(j&k) && !(k&(k>>1)))? (f[i][j]+f[i+1][k]) : f[i+1][k])%=P; return f[M+1][0];}int main(){ N=read(); bin[0]=1; for (int i=1; i<=20; i++) bin[i]=bin[i-1]<<1; for (int i=1; i<=N; i++) if (!visit[i]) (ANS*=DP(i))%=P; printf("%lld\n",ANS); return 0;}
断断续续写了2节课....一开始边界搞得有问题特别不科学.....这是弱智，
【BZOJ-2732】集合选数 状压DP （思路题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。