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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj3530】【Sdoi2014】【数数】  

2014-05-08 10:51:53|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:给一个数N和一个数字串集合,要求找出这样的数的个数,它满足:
   1)小于等于N
   2)子串不包含集合中的数字串。

   N的长度小于等于1200,集合大小小于等于100,集合的数字串的总长度小于等于1500。 

   0.0文本生成器的即视感恩...
   咱们用这些数字串建立AC自动机,建立的时候咱们给每一个节点记录一个能够沿着fail指针走到的最近的节点,然后凡是有这个节点的节点全都不能走,咱们称之为终止节点【走了的话显然就包含了这些集合中的串了】,然后咱们的一个数在AC自动机只要不走到那些终止节点就是一个答案。然后就是DP了...
    下面这种方法略脑洞,而且比较麻烦...可以跳过。= =

    {
    咱们按照上一题的启示,可以把N拆成N~100..00,99..99~10..00这样子的...然后假设N有l位,问题就变成了走1~l-1步不碰到禁止节点的方案数,和从某个节点走x步不经过禁止节点的方案数。前面一个dp,AC自动机状态数l,然后就是O(lL)的dp。可以承受,这个可以通过BFS得到。然后剩下的就是沿着N走自动机,然后每走到一个节点,问题变成了从这个节点出发走K步可以走到多少个节点【不经过禁止节点】,这个如果后面处理的话复杂度是O(L^2n)的,感觉不太好恩..实际上咱们可以再加一维,f[i][j][k],i=0表示走到节点j k步的方案数。然后i=1表示从N的路径的某个节点出发走k步到j的复杂度,然后这样子就不会增加复杂度了恩...咱们一开始的时候搜的时候处理一下就可以了。这样子复杂度就是O(IL)【话说好像变量搞混了额...= =】
    }

   【题解君
    实际上咱们的确可以类似数位DP地把N以内的数分类。比如
    N=141267的时候,拆分成 141267~100000,99999~10000,9999~1000,999~100,99~10,9~1
    对于除了第一个之外的,咱们可以裸地DP出来,只要注意转移到的不是禁止节点,以及第一次转移的时候不能走0即可。
    然后咱们关键就是考虑第一种,上面脑洞里面的那种方法会算重复一些...咱们需要分开更新额0.0..咱们设f[0][i][j]表示到节点i j步,且走过的字符串是N的前缀的方案,实际上就是1...然后咱们dp的时候,用 f[0][i][j]更新 f[0][i+1][Ni+1],用f[0][i][j]或f[1][i][j]更新 f[1][i+1][k]。然后最后统计所有的f[][len][]。

     然后这里的DP...咱一开始想的是bfs+HASH...但是略难写= =然后翻出以前的文本生成器的写法= =发现咱果然傻×了,咱们只需要先枚举走的步数,然后从0~tot的枚举节点就可以了= =因为这个顺序必然满足决策的先后顺序的,就不需要什么bfs了。
======================

program bzoj3530; const maxn=1510; maxnn=maxn*maxn; modd=1000000007; type node=record go:array[0..9]of longint; fai,las:longint; stop:boolean; end; var ac:array[0..maxn+100]of node; s,n:ansistring; m,tot:longint; que:array[0..maxnn]of longint; f:array[0..1,0..maxn,0..maxn]of int64; ans:int64; procedure insert; var i,j,tmp,len:longint; begin tmp:=0; len:=length(s); for i:=1 to len do begin j:=ord(s[i])-ord('0'); if ac[tmp].go[j]<>0 then tmp:=ac[tmp].go[j] else begin inc(tot); ac[tmp].go[j]:=tot; ac[tot].stop:=false; tmp:=tot; end; end; ac[tmp].stop:=true; end; procedure bfs; var i,l,r,u,v,tmp:longint; begin readln(n); tot:=0;ac[0].stop:=false; readln(m); for i:=1 to m do begin readln(s); insert; end; ac[0].fai:=0;ac[0].las:=0; l:=0;r:=0; for i:=0 to 9 do if ac[0].go[i]<>0 then begin que[r]:=ac[0].go[i]; ac[que[r]].fai:=0; ac[que[r]].las:=0; inc(r); end; while l<r do begin u:=que[l]; inc(l); for i:=0 to 9 do if ac[u].go[i]<>0 then begin v:=ac[u].go[i]; tmp:=ac[u].fai; while (tmp<>0)and(ac[tmp].go[i]=0)do tmp:=ac[tmp].fai; tmp:=ac[tmp].go[i]; ac[v].fai:=tmp; if ac[u].stop then ac[v].las:=u else ac[v].las:=ac[u].las; if ac[v].las<>0 then ac[v].stop:=true; que[r]:=v; inc(r); end; end; end; procedure init; var tmp,i,len,j,k,u,r:longint; flag1,flag2:boolean; begin bfs; len:=length(n); ans:=0; fillchar(f,sizeof(f),0); fillchar(que,sizeof(que),0); for i:=0 to tot do for j:=0 to 9 do begin k:=i; while (k<>0)and(ac[k].go[j]=0)do k:=ac[k].fai; k:=ac[k].go[j]; ac[i].go[j]:=k; end; f[0][0][0]:=1; for i:=0 to len-2 do for j:=0 to tot do for k:=0 to 9 do begin if (i=0)and(k=0)then continue; u:=ac[j].go[k]; if ac[u].stop then continue; f[0][u][i+1]:=f[0][u][i+1]+f[0][j][i]; if f[0][u][i+1]>=modd then dec(f[0][u][i+1],modd); end; for i:=1 to len-1 do for j:=0 to tot do begin ans:=ans+f[0][j][i]; if ans>=modd then ans:=ans-modd; end; fillchar(f,sizeof(f),0); f[1][0][0]:=1; for i:=0 to len-1 do for j:=0 to tot do if not ac[j].stop then for k:=0 to 9 do begin if (i=0)and(k=0)then continue; if (f[1][j][i]<>0)then if k<ord(n[i+1])-ord('0')then begin u:=ac[j].go[k]; if ac[u].stop then continue; f[0][u][i+1]:=f[0][u][i+1]+f[1][j][i]; if f[0][u][i+1]>=modd then dec(f[0][u][i+1],modd); end else if k=ord(n[i+1])-ord('0')then begin u:=ac[j].go[k]; if ac[u].stop then continue; f[1][u][i+1]:=f[1][u][i+1]+f[1][j][i]; if f[1][u][i+1]>=modd then dec(f[1][u][i+1],modd); end; u:=ac[j].go[k]; if ac[u].stop then continue; f[0][u][i+1]:=f[0][u][i+1]+f[0][j][i]; if f[0][u][i+1]>=modd then dec(f[0][u][i+1],modd); end; for i:=0 to tot do begin ans:=ans+f[0][i][len]; ans:=ans+f[1][i][len]; if ans>=modd then dec(ans,modd); end; write(ans); end; begin init; end.
  评论这张
 
阅读(291)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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