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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2734][HNOI2012]集合选数  

2015-06-20 15:12:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2734: [HNOI2012]集合选数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 676  Solved: 398
[Submit][Status][Discuss]

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}。

Solution

对于一个数x,令2x为其左儿子,3x为其右儿子。
当x=1的时候张这样:
        1
      2  3
    4  6  9
  8  12  18  27
......
逆时针转45度
1 3 9 27
2 6 18
4 12
8
现在就变成了任意两个相邻的数字不能同时取,就是BZOJ1725了。
然而并不是所有的数都在这里,比如5和7。跟1一样再做一次就好了。

Code

/**************************************************************
    Problem: 2734
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:544 ms
    Memory:2156 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 100010
#define p 1000000001
int n,vis[N],map[20][20],a[20],i,j,s,tot[20],x,can[2048],t,et,la[2048],f[20][2048];long long ans=1;
struct E{int to,nxt;}e[N];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void calc(int s){int i,j,k;
    for(vis[map[1][1]=s]=1,i=2;map[i-1][1]<<1<=n;i++)vis[map[i][1]=map[i-1][1]<<1]=1;
    for(map[i][1]=0,x=i-1,i=1;map[i][1];map[i][j]=0,tot[i++]=j-1)
    for(j=2;map[i][j-1]*3<=n;j++)vis[map[i][j]=map[i][j-1]*3]=1;x=i-1;
    if(x==1&&tot[1]==1){ans=(ans<<1)%p;return;}
    memset(f,0,sizeof(f)),f[0][0]=1;
    for(s=1<<tot[1],i=1;i<=x;i++)a[i]=(1<<tot[i])-1;
    for(a[x+1]=i=0;i<=x;i++)
    for(j=1;j<=t;j++)if(f[i][can[j]])
    for(k=la[can[j]];k&&e[k].to<=a[i+1];k=e[k].nxt)if((e[k].to|a[i+1])==a[i+1])
    f[i+1][e[k].to]=(f[i+1][e[k].to]+f[i][can[j]])%p;
    ans=ans*f[x+1][0]%p;
}
int main(){
    for(scanf("%d",&n),map[1][1]=1,i=2;map[1][i-1]*3<=n;i++)map[1][i]=map[1][i-1]*3;
    for(s=1<<i-1,i=s-1;i>=0;i--)if((i&(i<<1))==0)can[++t]=i;
    for(i=1;i<=t;i++)
    for(j=1;j<=t;j++)if((can[i]&can[j])==0)add(can[i],can[j]);
    for(i=1;i<=n;i++)if(!vis[i])calc(i);
    printf("%lld\n",ans);
}
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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