首页 > 其他 > 详细

bzoj2734 集合选数

时间:2016-01-16 19:24:14      阅读:95      评论:0      收藏:0      [点我收藏+]

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}有多少个满足上述约束条件 的子集。

状压dp

将问题转化为在求图上选不相邻的点的总方案数

1 3 9 27 81
2 6 18 54 162
4 12 36 108 324
8 24 72 216 ...
16 48 144 ...  

 

 

 

 

5 15 45 135
10 30 90 270
20 60 180 540
40 120 360 ...

 

 

 

7 21 63
14 42 126
28 84 252

 

 

 

...

取每个表中不超过n的部分分别计算方案数

每个表水平方向最多11列,竖直方向最多17行

由于不同表中选数互不干扰,将每个表的方案数相乘即为最终答案

#include<cstdio>
#define P 1000000001
int n;
long long f[24][2048];
bool hf[2048];
bool d[100005];
long long Ans=1;
int main(){
    f[0][0]=1;
    for(int i=0;i<2048;i++)if(!(i&(i>>1))&&!(i&(i<<1)))hf[i]=1;
    scanf("%d",&n);
    for(int w=1;w<=n;w++){
        if(d[w])continue;
        int pp=1,ii=1;
        long long ans=0;
        for(int i=w;i<=n;i+=i,ii++){
            int a=0,b=i;
            while(b<=n)d[b]=1,b*=3,a++;
            int pn=1<<a;
            for(int j=0;j<pn;j++){
                f[ii][j]=0;
                for(int k=0;k<pp;k++)
                    if(hf[j]&&hf[k]&&!(j&k))(f[ii][j]+=f[ii-1][k])%=P;
            }
            pp=pn;
        }
        ii--;
        for(int i=0;i<pp;i++)(ans+=f[ii][i])%=P;
        Ans*=ans;
        Ans%=P;
    }
    printf("%lld",Ans);
    return 0;
}

 

bzoj2734 集合选数

原文:http://www.cnblogs.com/ccz181078/p/5135983.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!