首页 > 代码库 > BZOJ2734: [HNOI2012]集合选数

BZOJ2734: [HNOI2012]集合选数

2024-07-20 01:34:03   219人阅读

2734: [HNOI2012]集合选数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 505  Solved: 287
[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}。

HINT

 

Source

day2

题解：
不能再神的做法。。。
1 3 9 
2 6 18
。。。。
然后就转化成了不能选两个相邻的数的方案数了。。。状压搞定
代码：
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define mod 100000000119 using namespace std;20 inline int read()21 {22     int x=0,f=1;char ch=getchar();23     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}25     return x*f;26 }27 int n,num[20];28 ll f[20][1<<12];29 bool v[maxn];30 ll get(int x)31 {32     int m=0;33     memset(num,0,sizeof(num));34     memset(f,0,sizeof(f));35     f[0][0]=1;36     while(x<=n)37     {38         m++;39         int xx=x;40         while(xx<=n)41         {42             num[m]++;v[xx]=1;xx*=3;43         }44         for(int i=0;i<1<<num[m];i++)45         {46          int j;47          for(j=1;j<num[m];j++)if((i&(1<<(j-1)))&&(i&(1<<j)))break;    48          if(j!=num[m])continue;49          for(j=0;j<1<<num[m-1];j++)if(!(i&j))f[m][i]=(f[m][i]+f[m-1][j])%mod;50         }51         x*=2;52     }53     ll t=0;54     for(int i=0;i<1<<num[m];i++)t=(t+f[m][i])%mod;55     return t;56 }57 int main()58 {59     freopen("input.txt","r",stdin);60     freopen("output.txt","w",stdout);61     n=read();62     ll ans=1;63     for(int i=1;i<=n;i++)if(!v[i])ans=(ans*get(i))%mod;64     printf("%lld\n",ans);65     return 0;66 }
View Code

 UPD:我说我的程序怎么跑得贼慢。。。就因为我每次就memset吗？。。。

还有一个就是判断 i 中是否有两个连续的1，只要判断 i&（i<<1)是否为0即可

 

BZOJ2734: [HNOI2012]集合选数


联系
我们