Bzoj2734 [hnoi2012]集合选数

Posted by yjjr's blog on February 6, 2018

标签:状压DP

Description

《集合论与图论》这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以下条件的子集:若 x在该子集中,则 2x 3x不能在该子集中。同学们不喜欢这种具有枚举性 质的题目,于是把它变成了以下问题:对于任意一个正整数 n≤100000,如何求出{1, 2,..., n}的满足上述约束条件的子集的个数(只需输出对 1,000,000,001 取模的结果),现在这个问题就 交给你了。 
 

Input

 只有一行,其中有一个正整数n30%的数据满足 n≤20 

Output
 
仅包含一个正整数,表示{1, 2,..., n}有多少个满足上述约束条件 的子集。 

Sample Input

4                       

Sample Output

8

【样例解释】

8个集合满足要求,分别是空集,{1}{14}{2}{23}{3}{34}{4}

 

题意:定义一个符合要求的集合为a2a,a3a不能同时存在,{x|1<=x<=n}的所有子集中有多少个符合要求

 

可以列出来一个奇奇怪怪的矩阵

1      3 9

2      6 18

4      12 36…….

这个矩阵向右*2,向下*3,矩阵中任何两个相邻的数的x倍都不能出现在同一个集合中

可以将方案数状压DP,最后将方案数用乘法原理相乘就可以了

F[i][j]表示前i行且第i行状态为j时的方案数,转化为状压经典裸题

好妙的一道题呐

 

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const LL mod=1000000001;
const int maxn=20;
LL bin[maxn],n,a[maxn][maxn],b[maxn],f[maxn][1<<12],ans=1;
bool mark[100006];

LL cal(LL x){
	mem(b,0);
	a[1][1]=x;
	rep(i,2,18)
		if(a[i-1][1]*2<=n)a[i][1]=a[i-1][1]*2;
			else a[i][1]=n+1;
	rep(i,1,18)
		rep(j,2,11)
			if(a[i][j-1]*3<=n)a[i][j]=a[i][j-1]*3;
				else a[i][j]=n+1;//扩展n以内的x矩阵 
	rep(i,1,18)
		rep(j,1,11)
			if(a[i][j]<=n)b[i]+=bin[j-1],mark[a[i][j]]=1;
	rep(i,0,18)
		rep(x,0,b[i])f[i][x]=0;
	f[0][0]=1;
	rep(i,0,17)
		rep(x,0,b[i])
			if(f[i][x])
				rep(y,0,b[i+1])
			        if(((x&y)==0)&&((y&(y>>1))==0))f[i+1][y]=(f[i+1][y]+f[i][x])%mod;
    return f[18][0];
}
int main()
{
	scanf("%lld",&n);
	bin[0]=1;
	rep(i,1,19)bin[i]=bin[i-1]<<1;
	rep(i,1,n)
	    if(!mark[i])ans=(ans*cal(i))%mod;//mark[i]表示这个数是否已经在集合内 
	printf("%lld\n",ans);
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr