結果

問題 No.1050 Zero (Maximum)
ユーザー nadeshinonadeshino
提出日時 2020-05-08 22:26:08
言語 Nim
(2.0.2)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 3,905 bytes
コンパイル時間 2,629 ms
コンパイル使用メモリ 71,964 KB
実行使用メモリ 5,400 KB
最終ジャッジ日時 2023-09-17 03:07:28
合計ジャッジ時間 3,749 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 16 ms
4,376 KB
testcase_03 AC 10 ms
4,380 KB
testcase_04 AC 42 ms
4,860 KB
testcase_05 AC 46 ms
4,688 KB
testcase_06 AC 21 ms
4,384 KB
testcase_07 AC 25 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 13 ms
4,380 KB
testcase_10 AC 60 ms
5,128 KB
testcase_11 AC 41 ms
4,588 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 64 ms
5,072 KB
testcase_17 AC 71 ms
5,400 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/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]
0