結果

問題 No.1311 Reverse Permutation Index
ユーザー 👑 obakyanobakyan
提出日時 2021-07-31 19:06:59
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 1,313 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 09:40:19
合計ジャッジ時間 1,002 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local ffi = require("ffi")
local C = ffi.C
ffi.cdef[[
long long atoll(const char*);
]]

local function lltonumber(str)
  return C.atoll(str)
end


local function getpattern(n, patall, idx)
  local used = {}
  local retary = {}
  local div = patall
  for i = 1, n do used[i] = false end
  for i = n, 1, -1 do
    div = div / (1LL * i)
    local v_idx = idx / div
    idx = idx % div
    local tmp_idx = 0
    for j = 1, n do
      if not used[j] then
        if tmp_idx == v_idx then
          table.insert(retary, j)
          used[j] = true
          break
        else
          tmp_idx = tmp_idx + 1
        end
      end
    end
  end
  return retary
end

local n, len = io.read():match("(%d+) (%d+)")
n = lltonumber(n)
len = tonumber(len)
local tot = 1LL
for i = 2, len do
  tot = tot * i
end
local ary = getpattern(len, tot, n)
-- print(table.concat(ary, " "))
local ainv = {}
for i = 1, len do ainv[i] = 0 end
for i = 1, len do
  ainv[ary[i]] = i
end
-- print(table.concat(ainv, " "))
local used = {}
for i = 1, len do used[i] = false end
local ret = 0LL
for i = 1, len do
  local add = 1LL
  for j = i + 1, len do
    add = add * (j - i)
  end
  for j = 1, ainv[i] - 1 do
    if not used[j] then
      ret = ret + add
    end
  end
  used[ainv[i]] = true
end
ret = tostring(ret):gsub("LL", "")
print(ret)
0