結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-11-03 14:20:56 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 538 ms / 2,000 ms |
コード長 | 5,677 bytes |
コンパイル時間 | 3,127 ms |
コンパイル使用メモリ | 74,872 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-13 03:47:08 |
合計ジャッジ時間 | 18,301 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(5, 5) Warning: imported and not used: 'algorithm' [UnusedImport] /home/judge/data/code/Main.nim(13, 5) Warning: imported and not used: 'strformat' [UnusedImport] /home/judge/data/code/Main.nim(15, 5) Warning: imported and not used: 'sugar' [UnusedImport] /home/judge/data/code/Main.nim(8, 5) Warning: imported and not used: 'heapqueue' [UnusedImport]
ソースコード
when not declared ATCODER_YULY3HEADER_HPP:const ATCODER_YULY3HEADER_HPP* = 1importalgorithm,bitops,deques,heapqueue,math,macros,sets,sequtils,strformat,strutils,sugar,tablesproc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =# Looks for the last statement of the last statement, etc...case n.kindof nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:result[0] = copyNimTree(n)result[1] = copyNimTree(n)result[2] = copyNimTree(n)for i in ord(n.kind == nnkCaseStmt)..<n.len:(result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:result[0] = copyNimTree(n)result[1] = copyNimTree(n)result[2] = copyNimTree(n)if n.len >= 1:(result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],res, bracketExpr)of nnkTableConstr:result[1] = n[0][0]result[2] = n[0][1]if bracketExpr.len == 1:bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(bindSym"typeof", newEmptyNode())])template adder(res, k, v) = res[k] = vresult[0] = getAst(adder(res, n[0][0], n[0][1]))of nnkCurly:result[2] = n[0]if bracketExpr.len == 1:bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))template adder(res, v) = res.incl(v)result[0] = getAst(adder(res, n[0]))else:result[2] = nif bracketExpr.len == 1:bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))template adder(res, v) = res.add(v)result[0] = getAst(adder(res, n))macro collect*(init, body: untyped): untyped =runnableExamples:import sets, tableslet data = @["bird", "word"]## seq:let k = collect(newSeq):for i, d in data.pairs:if i mod 2 == 0: dassert k == @["bird"]## seq with initialSize:let x = collect(newSeqOfCap(4)):for i, d in data.pairs:if i mod 2 == 0: dassert x == @["bird"]## HashSet:let y = initHashSet.collect:for d in data.items: {d}assert y == data.toHashSet## Table:let z = collect(initTable(2)):for i, d in data.pairs: {i: d}assert z == {0: "bird", 1: "word"}.toTablelet res = genSym(nskVar, "collectResult")expectKind init, {nnkCall, nnkIdent, nnkSym}let bracketExpr = newTree(nnkBracketExpr,if init.kind == nnkCall: init[0] else: init)let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)if bracketExpr.len == 3:bracketExpr[1][1] = keyTypebracketExpr[2][1] = valueTypeelse:bracketExpr[1][1] = valueTypelet call = newTree(nnkCall, bracketExpr)if init.kind == nnkCall:for i in 1 ..< init.len:call.add init[i]result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)proc nextString*(f: auto = stdin): string =var get = falseresult = ""while true:let c = f.readCharif c.int > ' '.int:get = trueresult.add(c)elif get: returnproc nextInt*(f: auto = stdin): int = parseInt(f.nextString)proc nextFloat*(f: auto = stdin): float = parseFloat(f.nextString)proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or mproc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and mproc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor mproc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl mproc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr mproc modPow*(a: int, k: Natural, MOD = 10^9 + 7): int =vara = ak = kresult = 1while k > 0:if bitand(k, 1) == 1:result = floorMod(result*a, MOD)a = floorMod(a*a, MOD)k = k shr 1proc modInv*(a: int, MOD = 10^9 + 7): int =return modPow(a, MOD - 2, MOD)proc matVecMul*(A: seq[seq[int]], B: seq[int], MOD = 10^9 + 7): seq[int] =let N = B.lenresult = newSeq[int](N)for i in 0..<N:for j in 0..<N:result[i] = floorMod(result[i] + floorMod(A[i][j]*B[j], MOD), MOD)proc matMul*(A, B: seq[seq[int]], M = 10^9 + 7): seq[seq[int]] =letN0 = A.lenN1 = B[0].lenN2 = A[0].lenresult = newSeqWith(N0, newSeq[int](N1))for i in 0..<N0:for j in 0..<N1:for k in 0..<N2:result[i][j] = floorMod(result[i][j] + A[i][k]*B[k][j], M)proc matPow*(A: seq[seq[int]], K: Natural, M = 10^9 + 7): seq[seq[int]] =let N = len(A)varA = AK = Kresult = newSeqWith(N, newSeq[int](N))for i in 0..<N:result[i][i] = 1while K > 0:if bitand(K, 1) == 1:result = matMul(result, A, M)A = matMul(A, A, M)K = K shr 1when isMainModule:const MOD = 10^9 + 7var T = nextInt()var ans: seq[int]for _ in 0..<T:var N = nextInt()var mat = newSeqWith(6, newSeq[int](6))for i in 0..2:for j in 0..2:if i == j:mat[i][j] = 1mat[i + 3][j] = 3else:mat[i][j + 3] = 1var vec = matPow(mat, N).matVecMul(@[1, 0, 0, 3, 0, 0])ans.add(modInv(modPow(3, N + 1))*vec[3] mod MOD)echo ans.join("\n")