結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
👑 |
提出日時 | 2021-08-06 12:20:30 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 373 ms / 5,000 ms |
コード長 | 2,724 bytes |
コンパイル時間 | 413 ms |
コンパイル使用メモリ | 6,688 KB |
実行使用メモリ | 22,528 KB |
最終ジャッジ日時 | 2024-09-17 00:28:18 |
合計ジャッジ時間 | 9,159 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
local mfl = math.floorlocal TFFT = {}TFFT.initialize = function(self)self.size = 18-- 2^18self.n = 262144-- 1007681537: prime,-- 1007681537 % 262144 = 1self.mod = 1007681537-- (6161^262144) % mod = 1, (6161^131072) % mod ~= 1self.w = 6161-- (1007677693 * 262144) % mod = 1self.ninv = 1007677693-- (534835031 * 6161) % mod = 1self.winv = 534835031self.p2 = {1}for i = 2, self.size doself.p2[i] = self.p2[i - 1] * 2endself.binv = {}for i = 1, self.n dolocal y, z = 0, i - 1for j = 1, self.size doy = y + (z % 2) * self.p2[self.size + 1 - j]z = mfl(z / 2)endself.binv[i] = y + 1endself.wmul = {1}for i = 2, self.n doself.wmul[i] = self:mul(self.wmul[i - 1], self.w)endself.winvmul = {1}for i = 2, self.n doself.winvmul[i] = self:mul(self.winvmul[i - 1], self.winv)endend-- (44893^2) % 1007681537 = 18375-- 1007681537 = 22446 * 44893 + rem(13259)-- x0, y0 <= 44892-- x1, y1 <= 22446-- max(x1y1*18375+(x1y0+x0y1)*44893+x0y0) < 10^14TFFT.mul = function(self, x, y)local x0, y0 = x % 44893, y % 44893local x1, y1 = mfl(x / 44893), mfl(y / 44893)return (x1 * y1 * 18375 + (x1 * y0 + x0 * y1) * 44893 + x0 * y0) % self.modendTFFT.add = function(self, x, y) return (x + y) % self.mod endTFFT.fft_common = function(self, ary, wmul)local ret = {}for i = 1, self.n doret[i] = ary[self.binv[i]]endfor i = 1, self.size dolocal step_size = self.p2[i]local step_count = self.p2[self.size + 1 - i]for istep = 1, step_count dolocal ofst = (istep - 1) * step_size * 2for j = 1, step_size dolocal a1, a2 = ret[ofst + j], ret[ofst + step_size + j]ret[ofst + j] = self:add(a1, self:mul(a2, wmul[1 + (j - 1) * step_count]))ret[ofst + step_size + j] = self:add(a1, self:mul(a2, wmul[1 + (j + step_size - 1) * step_count]))endendendreturn retendTFFT.fft = function(self, ary)return self:fft_common(ary, self.wmul)endTFFT.ifft = function(self, ary)local ret = self:fft_common(ary, self.winvmul)for i = 1, self.n doret[i] = self:mul(ret[i], self.ninv)endreturn retendlocal n, q = io.read("*n", "*n")TFFT:initialize()local a, b = {}, {}for i = 1, TFFT.n doa[i] = 0b[i] = 0endfor i = 1, n doa[i] = io.read("*n")endfor i = 1, q dolocal r = io.read("*n")if r == 0 thenb[1] = b[1] + 1elseb[n + 1 - r] = b[n + 1 - r] + 1endendlocal at = TFFT:fft(a)local bt = TFFT:fft(b)for i = 1, TFFT.n doat[i] = TFFT:mul(at[i], bt[i])endlocal c = TFFT:ifft(at)for i = 1, n doc[i] = c[i] + c[i + n]io.write(c[i])io.write(i == n and "\n" or " ")end