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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2004】【Hnoi2010】【公共线路Bus】  

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

  下载LOFTER 我的照片书  |
    0.0表示开做神题之后觉得咱的FFT还需要蹭细节额.....【其实就是没理解清...
    这个的模型转换咱觉得是非常巧妙的了...一下子把一道不可做题变成一道水题....【其实是眼力太弱...

    题目大意:给出一个长度为N的数列,在里面填1~K,要求每连续P个数这K个数都必须出现,特别要求前K位依次为1~K,后K位必须存在1~K,求方案数。
    至于为什么会转换成这个还是应该比较显然的吧... 
    那么就可以进行状压DP了,咱们用P位二进制表示状态,其中的1表示某辆公交车最后停下来的站点,然后0表示这不是任何一辆公交车最后停下来的地方。考虑转移,这里一开始不知道为什么必须开头1位必须为1,然后咱们来考虑..实际上这样子的话就保证了所有的方案是独立的(假设某个状态第一位是0的话,他显然也被算进了把这个0去掉之后的状态里,拿这两个转移就会有重复。 
    然后就是暴力出所有状态之间的转移...显然这里的转移会方便许多(因为必然是第一个1转移)然后就没了。
    恩呀...忘了...n<=10^9,但是可以矩阵转移...
===========================

program bzoj2004;
const modd=30031;
type arr=array[0..130,0..130]of int64;
var a,b,tmp:arr;
    st:array[0..600]of longint;
    n,kk,p,tot:longint;

procedure cheng(a:arr;var b,c:arr);
var i,j,k:longint;
begin
  for i:=1 to tot do
   for j:=1 to tot do
    begin
     c[i][j]:=0;
     for k:=1 to tot do
       c[i][j]:=c[i][j]+a[i][k]*b[k][j];
     while c[i][j]>modd do
       c[i][j]:=c[i][j] mod modd;
    end;
end;

procedure quickmod(n:longint);
begin
  while n<>0 do
   begin
     if n and 1=1 then cheng(a,b,a);
     n:=n shr 1;
     tmp:=b;
     cheng(tmp,tmp,b);
   end;
end;

function cal(p:longint):longint;
var sum:longint;
begin
  sum:=0;
  while p<>0 do
   begin
     if p and 1=1 then inc(sum);
     p:=p shr 1;
   end;
  exit(sum);
end;

function check(u,v:longint):boolean;
var w:longint;
begin
  u:=(u-(1 shl (p-1)))shl 1;
  w:=u xor v;
  if w-(w and (-w))=0 then exit(true)
                  else exit(false);
end;

procedure init;
var i,j:longint;
begin
  read(n,kk,p);
  tot:=0;
  for i:=1 shl (p-1) to (1 shl p)-1 do
   if cal(i)=kk then
    begin
      inc(tot);
      st[tot]:=i;
    end;
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  for i:=1 to tot do
   for j:=1 to tot do
    if check(st[i],st[j]) then
      b[i][j]:=1;
  for i:=1 to tot do a[i][i]:=1;
  quickmod(n-kk);
  i:=(1 shl p)-1-((1 shl (p-kk))-1);
  for j:=1 to tot do
   if st[j]=i then break;
  write(a[j][j]);
end;

begin
  init;
end.

    

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

历史上的今天

评论

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

页脚

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