結果

問題 No.599 回文かい
ユーザー 👑 obakyanobakyan
提出日時 2020-05-01 23:47:33
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 410 ms / 4,000 ms
コード長 5,047 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 5,300 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-26 16:41:50
合計ジャッジ時間 3,638 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 4 ms
4,380 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 4 ms
4,380 KB
testcase_07 AC 4 ms
4,380 KB
testcase_08 AC 4 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 182 ms
4,376 KB
testcase_11 AC 110 ms
4,380 KB
testcase_12 AC 206 ms
4,380 KB
testcase_13 AC 117 ms
4,380 KB
testcase_14 AC 306 ms
4,380 KB
testcase_15 AC 410 ms
4,376 KB
testcase_16 AC 363 ms
4,380 KB
testcase_17 AC 391 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,380 KB
evil_0.txt AC 299 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mfl, mce = math.floor, math.ceil
local mmi, mma = math.min, math.max
local mod = 1000000007

local function bmul(x, y)
  local x1, y1 = mfl(x / 31623), mfl(y / 31623)
  local x0, y0 = x - x1 * 31623, y - y1 * 31623
  return (x1 * y1 * 14122 + (x1 * y0 + x0 * y1) * 31623 + x0 * y0) % mod
end

local function badd(x, y)
  return (x + y) % mod
end

local TranSufA = {}
TranSufA.makeSufA = function(self)
  self.sufa = {}
  local n = #self.str
  local idx, tbl1, tbl2 = self.sufa, {}, {}
  local tmp_tbl = {}
  for i = 1, n do
    idx[i] = i
    tbl1[i] = self.str:sub(i, i):byte() - 95 -- "a" = 97
    tbl2[i] = 0
    tmp_tbl[i] = 0
  end
  idx[n + 1], tbl1[n + 1], tbl2[n + 1] = n + 1, 1, 0
  n = n + 1 -- add empty to last
  table.sort(idx, function(a, b) return tbl1[a] < tbl1[b] end)
  local step, stepflag = 1, true
  while step < n do
    local v = stepflag and tbl1 or tbl2
    local vd = stepflag and tbl2 or tbl1
    stepflag = not stepflag
    local stepdst = {}
    for i = 1, n do
      local dst = i + step
      if n < dst then dst = dst - n end
      stepdst[i] = dst
    end
    local left, major = 1, v[idx[1]]
    local minor_min = v[stepdst[idx[1]]]
    local minor_max = minor_min
    local minormap = {}
    local cur = 0
    for i = 1, n do
      local minor = v[stepdst[idx[i]]]
      if minormap[minor] then minormap[minor] = minormap[minor] + 1
      else minormap[minor] = 1
      end
      minor_min, minor_max = mmi(minor_min, minor), mma(minor_max, minor)
      local isend = i == n or major ~= v[idx[i + 1]]
      if isend then
        local right = i
        if left == right then
          cur = cur + 1
          vd[idx[left]] = cur
        elseif minor_min ~= minor_max then
          local minortbl = {}
          for k, _u in pairs(minormap) do table.insert(minortbl, k) end
          table.sort(minortbl)
          local offset = 0
          for i = 1, #minortbl do
            local cnt = minormap[minortbl[i]]
            minormap[minortbl[i]] = i
            minortbl[i] = offset -- reuse
            offset = offset + cnt
          end
          for j = left, right do
            local idxj = idx[j]
            local minor_idx = minormap[v[stepdst[idxj]]]
            local ofst = minortbl[minor_idx]
            ofst = ofst + 1
            minortbl[minor_idx] = ofst
            tmp_tbl[ofst] = idxj
            vd[idxj] = cur + minor_idx
          end
          cur = cur + #minortbl
          for j = left, right do
            idx[j] = tmp_tbl[j - left + 1]
          end
        else
          cur = cur + 1
          for j = left, right do
            vd[idx[j]] = cur
          end
        end
        if i < n then
          left, major = i + 1, v[idx[i + 1]]
          minor_min = v[stepdst[idx[i + 1]]]
          minor_max = minor_min
          minormap = {}
        end
      end
    end
    step = step * 2
  end
  -- remove empty from first (O(N))
  table.remove(self.sufa, 1)
  n = n - 1
  self.sufa_inv = {}
  for i = 1, n do self.sufa_inv[i] = 0 end
  for i = 1, n do
    self.sufa_inv[self.sufa[i]] = i
  end
end
TranSufA.makeLCPA = function(self)
  assert(self.sufa)
  local n = #self.sufa
  self.lcpa = {}
  local str, sufa, lcpa = self.str, self.sufa, self.lcpa
  for i = 1, n - 1 do lcpa[i] = 0 end
  local spos = 0
  for i = 1, n do
    local lcppos = self.sufa_inv[i]
    if lcppos < n then
      local len = spos
      local p1, p2 = sufa[lcppos], sufa[lcppos + 1]
      p1, p2 = p1 + spos, p2 + spos
      while p1 <= n and p2 <= n do
        if str:sub(p1, p1) == str:sub(p2, p2) then
          len = len + 1
          p1, p2 = p1 + 1, p2 + 1
        else break
        end
      end
      lcpa[lcppos] = len
      spos = mma(0, len - 1)
    end
  end
end

TranSufA.create = function(self, str)
  self.str = str
  self:makeSufA()
  self:makeLCPA()
end

TranSufA.new = function(str)
  local obj = {}
  setmetatable(obj, {__index = TranSufA})
  obj:create(str)
  return obj
end

local s = io.read()
local sa = TranSufA.new(s)
-- print(table.concat(sa.sufa, " "))
-- print(table.concat(sa.sufa_inv, " "))
-- print(table.concat(sa.lcpa, " "))
local n = #s
local hn = mfl(n / 2)
local offset = #s - hn
local dp = {}
for i = 1, hn + 1 do
  dp[i] = 1
end
for i = 1, hn do
  local src = offset + i
  local sufa_pos = sa.sufa_inv[src]
  local rev_src = n + 1 - src
  local len = 1000000007
  local pos = sufa_pos
  while pos < n do
    local dst = sa.sufa[pos + 1]
    len = mmi(len, sa.lcpa[pos])
    if dst <= rev_src and rev_src - dst + 1 <= len then
      local dpsrc = i - 1
      local dpdst = i - 1 + (rev_src - dst + 1)
      dp[dpdst + 1] = badd(dp[dpdst + 1], dp[dpsrc + 1])
    end
    pos = pos + 1
  end
  len = 1000000007
  pos = sufa_pos
  while 1 < pos do
    local dst = sa.sufa[pos - 1]
    len = mmi(len, sa.lcpa[pos - 1])
    if dst <= rev_src and rev_src - dst + 1 <= len then
      local dpsrc = i - 1
      local dpdst = i - 1 + (rev_src - dst + 1)
      dp[dpdst + 1] = badd(dp[dpdst + 1], dp[dpsrc + 1])
    end
    pos = pos - 1
  end
end
print(dp[hn + 1])
0