Submission #8087483

---

Source Code Expand

local mfl = math.floor
local mod = 1000000007
local function bmul(x, y)
  local x0, y0 = x % 31623, y % 31623
  local x1, y1 = mfl(x / 31623), mfl(y / 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 function getxor(x, y)
  local ret = 0
  local mul = 1
  while 0 < x or 0 < y do
    if (x % 2) + (y % 2) == 1 then
      ret = ret + mul
    end
    x, y, mul = mfl(x / 2), mfl(y / 2), mul * 2
  end
  return ret
end

local n, k = io.read("*n", "*n")
local lower = {}
local higher = {}
for i = 1, n do
  local a = io.read("*n")
  if a < 4096 then
    table.insert(lower, a)
  else
    table.insert(higher, a)
  end
end
local dp1, dp2 = {}, {}
for i = 1, 131072 do
  dp1[i] = 0
end
dp1[1] = 1
for ic = 1, #higher do
  for i = 1, 131072 do
    dp2[i] = 0
  end
  local v = higher[ic]
  for src = 0, 131071 do
    local dst = getxor(src, v)
    dp2[dst + 1] = dp1[src + 1]
  end
  for i = 1, 131072 do
    dp1[i] = badd(dp1[i], dp2[i])
  end
end
if k < 4096 then
  for ic = 1, #lower do
    for i = 1, 4096 do
      dp2[i] = 0
    end
    local v = lower[ic]
    for src = 0, 4095 do
      local dst = getxor(src, v)
      dp2[dst + 1] = dp1[src + 1]
    end
    for i = 1, 4096 do
      dp1[i] = badd(dp1[i], dp2[i])
    end
  end
  print(dp1[k + 1])
else
  for i = 1, 4096 do
    dp1[i] = 0
  end
  dp1[1] = 1
  for ic = 1, #lower do
    for i = 1, 4096 do
      dp2[i] = 0
    end
    local v = lower[ic]
    for src = 0, 4095 do
      local dst = getxor(src, v)
      dp2[dst + 1] = dp1[src + 1]
    end
    for i = 1, 4096 do
      dp1[i] = badd(dp1[i], dp2[i])
    end
  end
  local ret = 0
  for lowpos = 1, 4096 do
    local highpos = getxor(k, lowpos - 1) + 1
    ret = badd(ret, bmul(dp1[lowpos], dp1[highpos]))
  end
  print(ret)
end

Submission Info

Judge Result