結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
👑 |
提出日時 | 2022-08-12 13:50:42 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,689 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 6,944 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 16:31:25 |
合計ジャッジ時間 | 5,283 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
local mod = 1000000007local mfl = math.floorlocal function bmul(x, y)local x1, y1 = mfl(x / 31623), mfl(y / 31623)local x0, y0 = x - x1 * 31623, y - y1 * 31623return (x1 * y1 * 14122 + (x1 * y0 + x0 * y1) * 31623 + x0 * y0) % modendlocal function badd(x, y)return (x + y) % modendlocal function bsub(x, y)return x < y and x - y + mod or x - yend--[[a[i]: at Ab[i]: at B or Cc[i]: moving to Ad[i]: moving to B or Ca[i + 1] = 1/3 * a[i] + c[i]b[i + 1] = 1/3 * b[i] + d[i]c[i + 1] = 1/3 * b[i]d[i + 1] = 2/3 * a[i] + 1/3 * b[i]]]local mat = {}local tmpmat = {}for i = 1, 4 domat[i] = {}tmpmat[i] = {}endlocal vec = {}local tmpvec = {}local function matmat()for i = 1, 4 dofor j = 1, 4 dolocal v = 0for k = 1, 4 dov = badd(v, bmul(mat[i][k], mat[k][j]))endtmpmat[i][j] = vendendfor i = 1, 4 do for j = 1, 4 domat[i][j] = tmpmat[i][j]end endendlocal function matvec()for i = 1, 4 dolocal v = 0for k = 1, 4 dov = badd(v, bmul(mat[i][k], vec[k]))endtmpvec[i] = vendfor i = 1, 4 dovec[i] = tmpvec[i]endendlocal div3 = 333333336local div3_2 = 666666672local half = 500000004local function reset()vec[1], vec[2], vec[3], vec[4] = 1, 0, 0, 0for i = 1, 4 do for j = 1, 4 domat[i][j] = 0end endmat[1][1], mat[1][3] = div3, 1mat[2][2], mat[2][4] = div3, 1mat[3][2] = div3mat[4][1], mat[4][2] = div3_2, div3endlocal q = io.read("*n")for iq = 1, q dolocal n = io.read("*n")reset()while 0 < n doif n % 2 == 1 thenmatvec()endmatmat()n = mfl(n / 2)endprint(vec[1])end