bzoj 2734 集合选数

Written with StackEdit.

Description

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

Input

只有一行，其中有一个正整数 \(n\)，\(30\%\)的数据满足 \(n\leq20\)。

Output

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

Sample Input

Sample Output

【样例解释】

有\(8\) 个集合满足要求，分别是\(\emptyset\)，\(\{1\}\)，\(\{1，4\}\)，\(\{2\}\)，\(\{2，3\}\)，\(\{3\}\)，\(\{3，4\}\)，\(\{4\}\).

Solution

神仙构造题.
考虑构造这样的一个矩阵

\[\begin{pmatrix}
1 & 3 & 9 & 27 & ...\\
2 & 6 & 18 & 54 & ...\\
4 & 12 & 36 & 108 & ...\\
8 & 24 & 72 & 216 & ...\\
... & ... & ... & ... & ...\\
\end{pmatrix} \quad\]

其中一个数是它上边那个数的\(2\)倍,左边那个数的\(3\)倍.
原问题转化为从矩阵中选出一些互不相邻的数.
那么这个矩阵中的数是呈指数级增长的,规模不会超过\(20\).
使用经典状压\(dp\)处理,逐行考虑.
另,对于每个尚未出现过的数,需以它为左上角建一个矩阵,这样各个构造出的矩阵互不相交,利用乘法原理统计答案.

左上角的数增大时,矩阵没有填入数字的部分也不断增大.手动\(memset\).

#include<bits/stdc++.h>

using namespace std;

typedef long long LoveLive;

inline int read()

{

	int out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		{

			fh=-1;

			jp=getchar();

		}

	while (jp>='0'&&jp<='9')

		{

			out=out*10+jp-'0';

			jp=getchar();

		}

	return out*fh;

}

const int P=1e9+1;

inline int add(int a,int b)

{

	return (a + b) % P;

}

inline int mul(int a,int b)

{

	return 1LL * a * b % P;

}

const int MAXN=1e5+10;

int n;

int vis[MAXN];

int Martix[20][20];

int limit[20];//第i行的边界

int ans=1;

int r,c;

int judge(int st)

{

	int ls=0;

	while(st)

		{

			int p=st&1;

			if(p && ls)

				return 0;

			ls=p;

			st>>=1;

		}

	return 1;

}

vector<int> G;

void Build_Martix(int x)

{

	memset(Martix,-1,sizeof Martix);

	r=0,c=0;

	int p;

	for(int i=1;i<20;++i)

		{

			p=i==1?x:Martix[i-1][1]*2;

			if(p>n)

				{

					r=i-1;

					break;

				}

			Martix[i][1]=p;

			vis[p]=1;

			for(int j=2;j<20;++j)

				{

					p=Martix[i][j-1]*3;

					if(p>n)

						{

							c=max(c,j-1);

							limit[i]=j-1;

							break;

						}

					Martix[i][j]=p;

					vis[p]=1;

				}

		}

	G.clear();

	int S=1<<c;

	for(int i=0;i<S;++i)

		if(judge(i))

			G.push_back(i);

}

int f[20][1<<20];

inline int check(int x,int y)

{

	return !(x&y);

}

int dfs(int k,int st)//填好了前k行,且第k行状态为st的方案数.

{

	if(k==1)

		return 1;

	if(f[k][st]!=-1)

		return f[k][st];

	int &res=f[k][st];

	res=0;

	int S=(1<<limit[k-1])-1;

	for(int v=0;v<G.size();++v)

		{

			int i=G[v];

			if(i>S)

				break;

			if(check(i,st))

				res=add(res,dfs(k-1,i));

		}

	return res;

}

void solve(int x)//以x为左上角构造矩阵的方案数

{

	Build_Martix(x);

	for(int i=1;i<=r+1;++i)

		{

			int S=1<<limit[i];

			for(int j=0;j<S;++j)

				f[i][j]=-1;

		}

	//memset(f,-1,sizeof f);

	ans=mul(ans,dfs(r+1,0));

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

		if(!vis[i])

			solve(i);

	printf("%d\n",ans);

	return 0;

}

秒客网