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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2734】【Hnoi2012】【集合选数】  

2014-04-18 20:07:34|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:从1~n选出一些数球方案数,约定 x 选了,2x和3x就不能选。求方案数。
    一开始想的是树DP....然后发现这货不是树...咱们给每个限制的数之间连一条边,然后就可以DP出答案。这里实际上还要一种更好的做法:Matrix67神犇
    咱们按上面的数表来DP即可...具体做法是先扫出不是2,3的数,然后咱们可以迅速求出每一行的数的个数,然后设f[i][j]表示第i行的二进制状态为j的方案数,这里把空格全部设成0即可,也就是说咱们咱们的二进制是从最低位到高位是从左到右的。然后这样子做就可以了。其实还可以做得更好,那就是用滚动数组,用一个变换参数w即可,用w和w^1表示当前dp数组和上一个数组。
    然后就是状态的检验,上下的咱们直接and一下即可,然后关于某一个状态,咱们只要能判断能否有两个相邻的1即可,咱们把这个数左移一位,然后and一下,如果有相邻的1,必然不为0。 
    突然想起咱没有看插头DP的...赶紧去补一补...
==========================

program hnoi2012day2d;
const modd=1000000001;
var f:array[0..1,0..100010]of int64;
    c:array[0..100010]of longint;
    tot,n:longint;
    ans:int64;

procedure clear(w:longint);
var i:longint;
begin
  for i:=0 to n do f[w][i]:=0;
end;

function cal(p:longint):longint;
var ans:longint;
begin
  ans:=0;
  while p<=n do
   begin
     inc(ans);
     p:=p*2;
   end;
  exit(ans);
end;

procedure init;
var i,ii,j,k,w,len,lastlen:longint;
    tmp:int64;
begin
  read(n);
  tot:=0;w:=0;
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
   if (i mod 2<>0)and(i mod 3<>0)then
    begin
      inc(tot);
      c[tot]:=i;
    end;
  ans:=1;
  for k:=1 to tot do
   begin
     j:=c[k];
     len:=cal(j);
     for i:=0 to (1 shl len)-1 do
      if (i shl 1)and i=0 then
        f[w][i]:=1;
     lastlen:=len;
     j:=j*3;
     w:=w xor 1;
     while j<=n do
      begin
        len:=cal(j);
        for i:=0 to (1 shl len)-1 do
         if (i shl 1)and i=0 then
          begin
          f[w][i]:=0;
          for ii:=0 to (1 shl lastlen)-1 do
           if (ii shl 1)and ii=0 then
           if i and ii=0 then
            begin
             f[w][i]:=f[w][i]+f[w xor 1][ii];
             if f[w][i]>modd then f[w][i]:=f[w][i]-modd;
            end;
          end;
        w:=w xor 1;
        lastlen:=len;
        j:=j*3;
      end;
     tmp:=0;
     for i:=0 to (1 shl lastlen)-1 do
      if (i shl 1)and i=0 then
       begin
        tmp:=tmp+f[w xor 1][i];
        if tmp>modd then tmp:=tmp-modd;
       end;
     ans:=(ans*tmp)mod modd;
   end;
  write(ans);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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