Written with StackEdit.
Description
《集合论与图论》这门课程有一道作业题，要求同学们求出({1, 2, 3, 4, 5})的所有满足以 下条件的子集：若 (x) 在该子集中，则 (2x) 和 (3x) 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 (nleq 100000)，如何求出({1, 2,..., n}) 的满足上述约束条件的子集的个数（只需输出对 (1000000001) 取模的结果），现在这个问题就 交给你了。
Input
只有一行，其中有一个正整数 (n)，(30\%)的数据满足 (nleq20)。
Output
仅包含一个正整数，表示({1, 2,..., n})有多少个满足上述约束条件 的子集。
Sample Input
4
Sample Output
8
【样例解释】
有(8) 个集合满足要求，分别是(emptyset)，({1})，({1，4})，({2})，({2，3})，({3})，({3，4})，({4}).
Solution
- 神仙构造题.
- 考虑构造这样的一个矩阵
[egin{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
",ans);
return 0;
}