Submission #8088181

---

Source Code Expand

local mma = math.max
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 lowmax = 0
for i = 1, #lower do
  lowmax = mma(lowmax, lower[i])
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
local xors = {}
for i = 1, 2048 do
  xors[i] = {}
  for j = 1, i - 1 do
    xors[i][j] = getxor(i - 1, j - 1)
  end
  xors[i][i] = 0
end
for i = 1, 2048 do
  for j = i + 1, 2048 do
    xors[i][j] = xors[j][i]
  end
  for j = 2049, 4096 do
    xors[i][j] = xors[i][j - 2048] + 2048
  end
end
for i = 2049, 4096 do
  xors[i] = {}
  for j = 1, 2048 do
    xors[i][j] = xors[i - 2048][j] + 2048
  end
  for j = 2049, 4096 do
    xors[i][j] = xors[i - 2048][j - 2048]
  end
end
-- print(os.clock())
-- os.exit()
local lowmax2 = 1
while lowmax2 < lowmax do
  lowmax2 = lowmax2 * 2
end
if k < 4096 then
  for ic = 1, #lower do
    for i = 1, lowmax2 do
      dp2[i] = 0
    end
    local v = lower[ic]
    for src = 0, lowmax2 - 1 do
      local dst = xors[src + 1][v + 1]
      dp2[dst + 1] = dp1[src + 1]
    end
    for i = 1, lowmax2 do
      dp1[i] = badd(dp1[i], dp2[i])
    end
  end
  print(dp1[k + 1])
else
  for i = 1, lowmax2 do
    dp1[i] = 0
  end
  dp1[1] = 1
  for ic = 1, #lower do
    for i = 1, lowmax2 do
      dp2[i] = 0
    end
    local v = lower[ic]
    for src = 0, lowmax2 - 1 do
      local dst = xors[src + 1][v + 1]
      dp2[dst + 1] = dp1[src + 1]
    end
    for i = 1, lowmax2 do
      dp1[i] = badd(dp1[i], dp2[i])
    end
  end
  local ret = 0
  for lowpos = 1, lowmax2 do
    local highpos = getxor(k, lowpos - 1) + 1
    ret = badd(ret, bmul(dp1[lowpos], dp1[highpos]))
  end
  print(ret)
end

Submission Info

Judge Result