結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
![]() |
提出日時 | 2020-05-08 22:26:08 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 3,905 bytes |
コンパイル時間 | 3,164 ms |
コンパイル使用メモリ | 70,172 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 00:55:35 |
合計ジャッジ時間 | 4,109 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'algorithm' [UnusedImport]
ソースコード
import algorithm, macros, math, sequtils, strutils, tables# import bitops, lenientops, deques,# heapqueue, sets, sugarlet read* = iterator: string =while true: (for s in stdin.readLine.split: yield s)template input*(T: static[typedesc]): untyped =when T is int: read().parseIntelif T is float: read().parseFloatelif T is string: read()elif T is char: read()[0]macro dump*(args: varargs[typed]): untyped =result = newNimNode(nnkStmtList)for x in args:let s = toStrLit(x)result.add quote do: stderr.write `s`, " = ", `x`, " "result.add quote do: stderr.write "\n"proc `|=`*(n: var int, m: int) = n = n or mproc `|=`*(n: var bool, m: bool) = n = n or mproc `&=`*(n: var int, m: int) = n = n and mproc `&=`*(n: var bool, m: bool) = n = n and mproc `^=`*(n: var int, m: int) = n = n xor mproc `^=`*(n: var bool, m: bool) = n = n xor mproc `%=`*(n: var int, m: int) = n = n mod mproc `/=`*(n: var int, m: int) = n = n div mproc `<<=`*(n: var int, m: int) = n = n shl mproc `>>=`*(n: var int, m: int) = n = n shr mproc `<?=`*(n: var SomeNumber, m: SomeNumber) = n = min(n, m)proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))proc newSeq4*[T](n1, n2, n3, n4: Natural): seq[seq[seq[seq[T]]]] = newSeqWith(n1, newSeqWith(n2, newSeqWith(n3, newSeq[T](n4))))# -------------------------------------------------- #const modulus = 10 ^ 9 + 7type ModMatrix* = seq[seq[int]]proc initModMatrix*(N: Natural, M: Natural): ModMatrix =ModMatrix(newSeqWith(N, newSeq[int](M)))proc initModMatrix*(N: Natural): ModMatrix =ModMatrix(newSeqWith(N, newSeq[int](N)))proc initIdentityModMatrix*(N: Natural): ModMatrix =var R = initModMatrix(N)for i in 0 .. N - 1:R[i][i] = 1return Rproc toModMatrix*(A: seq[seq[int]]): ModMatrix =Aproc height*(A: ModMatrix): Natural {.inline.} =A.lenproc width*(A: ModMatrix): Natural {.inline.} =A[0].lenproc `+`*(A: ModMatrix, B: ModMatrix): ModMatrix =#assert height(A) == height(B)#assert width(A) == width(B)let (N, M) = (height(A), width(A))var R = initModMatrix(N, M)for i in 0 .. N - 1:for j in 0 .. M - 1:R[i][j] = A[i][j] + B[i][j]if R[i][j] >= modulus:R[i][j] -= modulusreturn Rproc `-`*(A: ModMatrix, B: ModMatrix): ModMatrix =#assert height(A) == height(B)#assert width(A) == width(B)let (N, M) = (height(A), width(A))var R = initModMatrix(N, M)for i in 0 .. N - 1:for j in 0 .. M - 1:R[i][j] = A[i][j] - B[i][j]if R[i][j] < 0:R[i][j] += modulusreturn Rproc `*`*(A: ModMatrix, B: ModMatrix): ModMatrix =#assert width(A) == height(B)let (N, P, M) = (height(A), width(A), width(B))var R = initModMatrix(N, M)for i in 0 .. N - 1:for j in 0 .. M - 1:for k in 0 .. P - 1:R[i][j] += A[i][k] * B[k][j]R[i][j] = R[i][j] mod modulusreturn Rproc `^`*(A: ModMatrix, k: Natural): ModMatrix =#assert height(A) == width(A)let N = height(A)var (A, k, R) = (A, k, initIdentityModMatrix(N))while k > 0:if bool(k and 1):R = R * AA = A * Ak = k shr 1return Rproc `+=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =A = A + Bproc `-=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =A = A - Bproc `*=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =A = A * Bproc `^=`*(A: var ModMatrix, k: Natural) {.inline.} =A = A ^ k# -------------------------------------------------- #let M, K = input(int)var A = initModMatrix(M, M)for j in 0 .. M - 1:for k in 0 .. M - 1:A[(j + k) mod M][j] += 1A[(j * k) mod M][j] += 1A ^= Kvar B = initModMatrix(M, 1); B[0][0] = 1let R = A * Becho R[0][0]