結果

問題 No.1554 array_and_me
ユーザー 👑 obakyan
提出日時 2021-08-12 21:42:03
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 162 ms / 2,000 ms
コード長 2,548 bytes
コンパイル時間 122 ms
コンパイル使用メモリ 6,812 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-10-02 02:51:12
合計ジャッジ時間 6,298 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

local bls, brs = bit.lshift, bit.rshift
local mod = 998244353
local mfl = math.floor
local function bmul(x, y)
local x0, y0 = x % 31596, y % 31596
local x1, y1 = mfl(x / 31596), mfl(y / 31596)
return (x1 * y1 * 62863 + (x1 * y0 + x0 * y1) * 31596 + x0 * y0) % mod
end
local function modpow(src, pow)
local res = 1
while 0 < pow do
if pow % 2 == 1 then
res = bmul(res, src)
pow = pow - 1
end
src = bmul(src, src)
pow = mfl(pow / 2)
end
return res
end
local function modinv(src)
return modpow(src, mod - 2)
end
local fact = {1}
local invs = {1}
local invfact = {1}
for i = 2, 100010 do
fact[i] = bmul(fact[i - 1], i)
invs[i] = bmul(mfl(mod / i), mod - invs[mod % i])
invfact[i] = bmul(invfact[i - 1], invs[i])
end
local Heapq = {}
Heapq.create = function(self, lt)
self.lt = lt
self.cnt = 0
self.t = {}
end
Heapq.push = function(self, v)
local hqlt = self.lt
local hqt = self.t
local c = self.cnt + 1
self.cnt = c
hqt[c] = v
while 1 < c do
local p = brs(c, 1)
if hqlt(hqt[c], hqt[p]) then
hqt[c], hqt[p] = hqt[p], hqt[c]
c = p
else
break
end
end
end
Heapq.pop = function(self)
local hqlt = self.lt
local hqt = self.t
local ret = hqt[1]
local c = self.cnt
hqt[1] = hqt[c]
c = c - 1
self.cnt = c
local p = 1
while true do
local d1, d2 = p * 2, p * 2 + 1
if c < d1 then break
elseif c < d2 then
if hqlt(hqt[d1], hqt[p]) then
hqt[d1], hqt[p] = hqt[p], hqt[d1]
end
break
else
if hqlt(hqt[d1], hqt[d2]) then
if hqlt(hqt[d1], hqt[p]) then
hqt[d1], hqt[p] = hqt[p], hqt[d1]
p = d1
else break
end
else
if hqlt(hqt[d2], hqt[p]) then
hqt[d2], hqt[p] = hqt[p], hqt[d2]
p = d2
else break
end
end
end
end
return ret
end
Heapq.new = function(lt)
local obj = {}
setmetatable(obj, {__index = Heapq})
obj:create(lt)
return obj
end
local q = io.read("*n")
for iq = 1, q do
local n, k = io.read("*n", "*n")
local a = {}
local box = {}
local asum = 0
for i = 1, n do
a[i] = io.read("*n")
box[i] = 1
asum = asum + a[i]
end
local hq = Heapq.new(function(x, y) return a[x] * box[y] > a[y] * box[x] end)
for i = 1, n do
hq:push(i)
end
local ret = bmul(fact[k], modpow(modinv(asum), k))
for i = 1, k do
local idx = hq:pop()
ret = bmul(ret, bmul(a[idx], invs[box[idx]]))
box[idx] = box[idx] + 1
hq:push(idx)
end
print(ret)
end
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0