注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2734(hnoi 2012)集合选数 set  

2013-02-09 17:16:07|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

方法太神了

我们先看这样一个矩阵

1 3

2 6

4 X

矩阵构造方法是左上角为1,往右走*3,往下走*2。

那么我们取得数在矩阵中就不能相邻,一个状压DP即可

不过5没有选进去啊!

而且所有能被5整除的也没选进去啊

所以左上角为5再做一遍

左上角为7,11等等再做一遍……

不需要筛素数那么麻烦,开个标记数组判断有木有用过就行了

不同矩阵间不影响,乘法原理搞一下即可

我状压DP插头DP学得好差的,本来犹豫要不要看代码

后来想了下还是自己写了

调对了样例和第二个数据后就过了

感觉对状压DP更熟练些了,不过插头DP还是各种纠结

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MOD 1000000001
#define MAXN 20
#define MAXM 15
#define N 100010
using namespace std;
typedef long long LL;
int n,r,c,map[MAXN][MAXM];
LL ans=1,F[2][1<<12];
bool use[N];
int get(int k,int p){  return k>>(p-1)&1;  }
void MakeMatrix(int p)
{
    memset(map,0,sizeof(map));
    r=c=1;
    for(int i=1,d1=p;d1<=n;i++,d1*=2)
    {
        use[d1]=true,map[i][1]=d1,r=max(r,i);
        for(int j=2,d2=d1*3;d2<=n;j++,d2*=3)
            use[d2]=true,map[i][j]=d2,c=max(c,j);
    }
}
LL Dp()
{
    LL ans=0;
    int mark=0,M=(1<<c)-1;
    for(int i=1;i<=M;i++)
        F[mark][i]=0;
    F[mark][0]=1;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            for(int k=0;k<=M;k++)
                F[mark^1][k]=0;
            for(int k=0;k<=M;k++)
            {
                if(F[mark][k]==0)  continue;
                F[mark^1][k<<1&M]=(F[mark^1][k<<1&M]+F[mark][k])%MOD;
                if(map[i][j]&&j==1&&!get(k,c))  F[mark^1][k<<1|1&M]=(F[mark^1][k<<1|1&M]+F[mark][k])%MOD;
                if(map[i][j]&&j!=1&&!get(k,c)&&!get(k,1))  F[mark^1][k<<1|1&M]=(F[mark^1][k<<1|1&M]+F[mark][k])%MOD;
            }
            mark^=1;
        }
    for(int i=0;i<=M;i++)
        ans=(ans+F[mark][i])%MOD;
    return ans;
}
void work()
{
    for(int i=1;i<=n;i++)
        if(use[i]==false)
        {
            MakeMatrix(i);
            ans=ans*Dp()%MOD;
        }
}
int main()
{
    scanf("%d",&n);
    work();
    printf("%lld\n",ans);
    return 0;
}


  评论这张
 
阅读(811)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017