bzoj 2734: [HNOI2012]集合选数 状压DP

时间:2021-08-24 06:34:09

2734: [HNOI2012]集合选数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 560  Solved: 321
[Submit][Status]

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}。
  神奇的排列组合问题,其中分成多个独立子问题,分别转化为矩阵,最有用乘法原理合并的思想可以用在很多题里面。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
#define MOD 1000000001
typedef long long qword;
int gcd(int x,int y)
{
return (x%y==)?y:gcd(y,x%y);
}
int pow(int x,int y)
{
int ret=;
while (y)
{
if (y&)ret*=x;
x*=x;
y>>=;
}
return ret;
}
qword pow_mod(qword x,int y)
{
qword ret=;
while(y)
{
if (y&)ret=ret*x%MOD;
x=x*x%MOD;
y>>=;
}
return ret;
}
int dp[][<<];
int ff[MAXN];
int main()
{
//freopen("input.txt","r",stdin);
int n,x,y;
scanf("%d",&n);
int i,j,k,ii;
qword ans=;
memset(ff,-,sizeof(ff));
for (i=;i<;i++)
{
if ((<<i)<MAXN)
ff[(<<i)]=i;
}
for (i=;i<MAXN;i++)
if (ff[i]==-)ff[i]=ff[i-];
for (ii=;ii<=n;ii++)
{
if (ii%== || ii%==)continue;
int l,r,mid;
l=,r=;
while (l+<r)
{
mid=(l+r)>>;
if ((qword)ii*pow(,mid)<=n)
l=mid;
else
r=mid;
}
memset(dp,,sizeof(dp));
dp[][]=;
x=ii;
for (i=;ii*(<<i>>)<=n;i++)//log(n)
{
for (j=;j<(<<r);j++)//2^(log3(n))
{
if (!dp[i-][j])continue;
for (k=;k<(<<r);k++)
{
if (j&k || (k&(k<<)))continue;
if ((qword)x*pow(,ff[k])>n)break;
dp[i][k]=(dp[i][k]+dp[i-][j])%MOD;
}
}
x*=;
}
qword res=;
for (j=;j<(<<r);j++)
{
res=(res+dp[i-][j])%MOD;
}
ans=ans*res%MOD;
}
printf("%lld\n",ans);
}