結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー nadeshino
提出日時 2020-04-07 08:53:20
言語 Nim
(2.2.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,774 bytes
コンパイル時間 4,121 ms
コンパイル使用メモリ 66,704 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 10:52:32
合計ジャッジ時間 4,471 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'algorithm' [UnusedImport]

ソースコード

diff # 

import algorithm, math, sequtils, strutils

let read* = iterator: string {.closure.} =
  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()

const modulus = 10 ^ 9 + 7
 
type ModMatrix* = seq[seq[int]]
 
proc initModMatrix*(N: Natural, M: Natural): ModMatrix =
  ModMatrix(newSeqWith(N + 1, newSeq[int](M + 1)))
 
proc initModMatrix*(N: Natural): ModMatrix =
  ModMatrix(newSeqWith(N + 1, newSeq[int](N + 1)))
 
proc initIdentityModMatrix*(N: Natural): ModMatrix =
  var R = initModMatrix(N)
  for i in 1 .. N:
    R[i][i] = 1
  return R
 
proc toModMatrix*(A: seq[seq[int]]): ModMatrix =
  A
 
proc height*(A: ModMatrix): Natural {.inline.} =
  A.high
 
proc width*(A: ModMatrix): Natural {.inline.} =
  A[1].high
 
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 1 .. N:
    for j in 1 .. M:
      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 1 .. N:
    for j in 1 .. M:
      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 1 .. N:
    for j in 1 .. M:
      for k in 1 .. P:
        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: ModMatrix): string =
  let (N, M) = (height(A), width(A))
  result = ""
  for i in 1 .. N:
    result = result & $A[i][1 .. M]
    if i < N:
      result.add("\n")
 
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 N = input(int)
var A = initModMatrix(2, 2)
A[1][1] = 1; A[1][2] = 1
A[2][1] = 1; A[2][2] = 0
var B = initModMatrix(2, 1)
B[1][1] = 1
B[2][1] = 0
let C = (A ^ N) * B
echo C[1][1] * C[2][1] mod modulus
0