結果

問題 No.1050 Zero (Maximum)
ユーザー nadeshinonadeshino
提出日時 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]

ソースコード

diff #
プレゼンテーションモードにする

import algorithm, macros, math, sequtils, strutils, tables
# import bitops, lenientops, deques,
# heapqueue, sets, sugar
let read* = iterator: string =
while true: (for s in stdin.readLine.split: yield s)
template input*(T: static[typedesc]): untyped =
when T is int: read().parseInt
elif T is float: read().parseFloat
elif 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 m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
proc `%=`*(n: var int, m: int) = n = n mod m
proc `/=`*(n: var int, m: int) = n = n div m
proc `<<=`*(n: var int, m: int) = n = n shl m
proc `>>=`*(n: var int, m: int) = n = n shr m
proc `<?=`*(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 + 7
type 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] = 1
return R
proc toModMatrix*(A: seq[seq[int]]): ModMatrix =
A
proc height*(A: ModMatrix): Natural {.inline.} =
A.len
proc width*(A: ModMatrix): Natural {.inline.} =
A[0].len
proc `+`*(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] -= modulus
return R
proc `-`*(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] += modulus
return R
proc `*`*(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 modulus
return R
proc `^`*(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 * A
A = A * A
k = k shr 1
return R
proc `+=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
A = A + B
proc `-=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
A = A - B
proc `*=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
A = A * B
proc `^=`*(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] += 1
A[(j * k) mod M][j] += 1
A ^= K
var B = initModMatrix(M, 1); B[0][0] = 1
let R = A * B
echo R[0][0]
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0