bzoj2734【HNOI2012】集合选数

时间：2023-03-08 16:13:40
bzoj2734【HNOI2012】集合选数

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}。

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;

}

相关文章