首页 > 代码库 > bzoj 2734: [HNOI2012]集合选数 状压DP
bzoj 2734: [HNOI2012]集合选数 状压DP
2734: [HNOI2012]集合选数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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 1000000001typedef long long qword;int gcd(int x,int y){ return (x%y==0)?y:gcd(y,x%y);}int pow(int x,int y){ int ret=1; while (y) { if (y&1)ret*=x; x*=x; y>>=1; } return ret;}qword pow_mod(qword x,int y){ qword ret=1; while(y) { if (y&1)ret=ret*x%MOD; x=x*x%MOD; y>>=1; } return ret;}int dp[30][1<<12];int ff[MAXN];int main(){ //freopen("input.txt","r",stdin); int n,x,y; scanf("%d",&n); int i,j,k,ii; qword ans=1; memset(ff,-1,sizeof(ff)); for (i=0;i<12;i++) { if ((1<<i)<MAXN) ff[(1<<i)]=i; } for (i=0;i<MAXN;i++) if (ff[i]==-1)ff[i]=ff[i-1]; for (ii=1;ii<=n;ii++) { if (ii%2==0 || ii%3==0)continue; int l,r,mid; l=0,r=12; while (l+1<r) { mid=(l+r)>>1; if ((qword)ii*pow(3,mid)<=n) l=mid; else r=mid; } memset(dp,0,sizeof(dp)); dp[0][0]=1; x=ii; for (i=1;ii*(1<<i>>1)<=n;i++)//log(n) { for (j=0;j<(1<<r);j++)//2^(log3(n)) { if (!dp[i-1][j])continue; for (k=0;k<(1<<r);k++) { if (j&k || (k&(k<<1)))continue; if ((qword)x*pow(3,ff[k])>n)break; dp[i][k]=(dp[i][k]+dp[i-1][j])%MOD; } } x*=2; } qword res=0; for (j=0;j<(1<<r);j++) { res=(res+dp[i-1][j])%MOD; } ans=ans*res%MOD; } printf("%lld\n",ans);}
bzoj 2734: [HNOI2012]集合选数 状压DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。