結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
👑 |
提出日時 | 2020-05-08 22:11:49 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,339 bytes |
コンパイル時間 | 91 ms |
コンパイル使用メモリ | 6,688 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 00:48:16 |
合計ジャッジ時間 | 1,045 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
local mod = 1000000007 local mfl = math.floor local function bmul(x, y) local x1, y1 = mfl(x / 31623), mfl(y / 31623) local x0, y0 = x - x1 * 31623, y - y1 * 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 m, k = io.read("*n", "*n") local mat = {} for i = 1, m do mat[i] = {} for j = 1, m do mat[i][j] = 0 end end for i = 1, m do local src = i - 1 for op = 0, m - 1 do local dst1, dst2 = (src + op) % m, (src * op) % m mat[src + 1][dst1 + 1] = mat[src + 1][dst1 + 1] + 1 mat[src + 1][dst2 + 1] = mat[src + 1][dst2 + 1] + 1 end end local vec = {1} for i = 2, m do vec[i] = 0 end local function matvec() local dst = {} for i = 1, m do local v = 0 for j = 1, m do v = badd(v, bmul(mat[i][j], vec[j])) end dst[i] = v end for i = 1, m do vec[i] = dst[i] end end local function matmat() local dst = {} for i = 1, m do dst[i] = {} for j = 1, m do local v = 0 for k = 1, m do v = badd(v, bmul(mat[i][k], mat[k][j])) end dst[i][j] = v end end for i = 1, m do for j = 1, m do mat[i][j] = dst[i][j] end end end while 0 < k do if k % 2 == 1 then matvec() end k = mfl(k / 2) matmat() end print(vec[1])