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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2160】【manacher算法】【拉拉队排练】  

2014-04-01 11:11:31|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题目大意:给出一个长度为n字符串,把所有以i为中心的最长回文子串按长度降序排序,取前K个,求前K个的长度的乘积。
    n<=10^6,k<=10^12
    其实学了Manacher就会发现这就是裸题了...咱们求完 manacher的p[]之后对之类似计数排序(因为它们的值都是1~n的),然后从计数的大到小统计即可,用快速幂统计的话复杂度O(nlogn)~

    这里根据题意只统计奇数的回文串。这是个给不好好读题的蒟蒻的一个trick= =。
=================================

program bzoj2160;
const maxn=1000010;
      modd=19930726;
var n,k,ans,sum:int64;
    a:array[0..maxn*3]of char;
    p:array[0..maxn*3]of int64;
    w:array[0..maxn*3]of longint;

function quickmod(p:int64;n:longint):int64;
var sum:int64;
begin
  sum:=1;
  while n<>0 do
   begin
     if n and 1=1 then sum:=(sum*p)mod modd;
     n:=n shr 1;
     p:=(p*p)mod modd;
   end;
  exit(sum);
end;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

procedure init;
var i,r,id:longint;
begin
  readln(n,k);
  a[1]:='#';a[0]:='$';
  for i:=1 to n do
   begin
     read(a[i shl 1]);
     a[i shl 1 xor 1]:='#';
   end;
  r:=0;id:=0;
  n:=n shl 1+1;
  fillchar(w,sizeof(w),0);
  fillchar(p,sizeof(p),0);
  for i:=1 to n do
   begin
     if r>i then
       p[i]:=min(p[id*2-i],r-i)
     else
       p[i]:=1;
     while (a[i+p[i]]=a[i-p[i]]) do inc(p[i]);
     if p[i]+i>r then
      begin
        r:=p[i]+i;
        id:=i;
      end;
     if i and 1=0 then inc(w[p[i]]);
   end;
  ans:=1;sum:=0;
  for i:=n+1 downto 2 do
   if i and 1=0 then
   begin
     if k>=w[i]+sum then
       begin
         ans:=ans*quickmod(i-1,w[i]+sum);
         if ans>modd then ans:=ans mod modd;
         dec(k,w[i]+sum);
         inc(sum,w[i]);
       end
     else
      begin
         ans:=ans*quickmod(i-1,k);
         if ans>modd then ans:=ans mod modd;
         k:=0;
      end;
     if k=0 then break;
   end;
  if k<>0 then write(-1)
          else write(ans);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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