結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー Kutimoti_T
提出日時 2018-10-19 21:26:28
言語 Nim
(2.2.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,345 bytes
コンパイル時間 3,173 ms
コンパイル使用メモリ 66,876 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 04:54:48
合計ジャッジ時間 3,973 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sequtils

proc IDE*(T : typedesc[int]) : int = return 0
proc PRO*(T : typedesc[int]) : int = return 1


type
  mint[M : static[int]] = object
    val : int

proc inv_mod*(A , M : int) : int =
  var
    a = A
    b = M
    x = 1
    u = 0
  while b > 0:
    var q = a div b
    var tmp = u
    u = x - q * u
    x = tmp
    tmp = b
    b = a - q * b
    a = tmp
  return (A + M) mod M    

proc newMint*[M](val : int) : mint[M] =
  return mint[M](val : (val mod M + M) mod M)

proc `$`*[M](m : mint[M]) : string = return m.val.intToStr
proc `+`*[M](a : mint[M] , b : mint[M]) : mint[M] = return mint[M](val : (a.val + b.val) mod M)
proc `-`*[M](a : mint[M] , b : mint[M]) : mint[M] = return mint[M](val : (a.val - b.val + M) mod M)
proc `*`*[M](a : mint[M] , b : mint[M]) : mint[M] = return mint[M](val : (a.val * b.val) mod M)
proc `/`*[M](a : mint[M] , b : mint[M]) : mint[M] = return mint[M](val : (a.val * inv_mod(b.val , M)) mod M)
proc `+`*[M](a : mint[M] , b : int) : mint[M]     = return mint[M](val : (a.val + b) mod M)
proc `-`*[M](a : mint[M] , b : int) : mint[M]     = return mint[M](val : (a.val - b + M) mod M)
proc `*`*[M](a : mint[M] , b : int) : mint[M]     = return mint[M](val : (a.val * b) mod M)
proc `/`*[M](a : mint[M] , b : int) : mint[M]     = return mint[M](val : (a.val * inv_mod(b , M)) mod M)
proc `+`*[M](a : int , b : mint[M]) : mint[M]     = return mint[M](val : (a + b.val) mod M)
proc `-`*[M](a : int , b : mint[M]) : mint[M]     = return mint[M](val : (a - b.val + M) mod M)
proc `*`*[M](a : int , b : mint[M]) : mint[M]     = return mint[M](val : (a * b.val) mod M)
proc `/`*[M](a : int , b : mint[M]) : mint[M]     = return mint[M](val : (a * inv_mod(b.val , M)) mod M)
proc `^`*[M](a : mint[M] , b : int) : mint[M] =
  var
    ans = newMint[M](1)
    c = a
    r = b
  while r > 0:
    if (r and 1) == 1: ans *= c
    c = c * c
    r = r shr 1
  return ans
type MM = mint[(int)(1e9 + 7)]

proc IDE*(T : typedesc[MM]) : MM = return MM(val : 0)
proc PRO*(T : typedesc[MM]) : MM = return MM(val : 1)



type Matrix*[T] = seq[seq[T]]

proc newMatrix*[T](h , w : int) : Matrix[T] =
    var mat : Matrix[T] = newSeqWith(h,newSeqWith(w , IDE(T)))
    return mat

proc `*`*[T](a , b : Matrix[T]) : Matrix[T] =
    var res = newMatrix[T](a.len , b[0].len)
    for i in 0..<a.len:
        for k in 0..<b.len:
            for j in 0..<b[0].len:
                res[i][j] = res[i][j] + a[i][k] * b[k][j]
    return res

proc `+`*[T](a , b : Matrix[T]) : Matrix[T] =
    var res = a
    for i in 0..<res.len:
        for j in 0..<res[0].len:
            res[i][j] += b[i][j]
    return res


proc `*`*[T](a : Matrix[T] , b : T) : Matrix[T] =
    var res = a
    for i in 0..<res.len:
        for j in 0..<res[0].len:
            res[i][j] += b
    return res

proc `^`*[T](a : Matrix[T] , n : int) : Matrix[T] =
    var 
        A = a
        res = newMatrix[T](a.len , a[0].len)
        r = n
    for i in 0..<res.len: res[i][i] = PRO(T)

    while r > 0:
        if (r and 1) == 1: res = res * A
        A = A * A
        r = r shr 1
    return res

# verify https://yukicoder.me/problems/no/718


import strutils

var
    N = stdin.readline.parseInt
    m = @[@[MM(val : 1) , MM(val : 0)]]
    mm = @[@[MM(val : 1) , MM(val : 1)] , @[MM(val : 1 ,) , MM(val : 0)]]
    a = (m * (mm ^ (N)))
echo a[0][0] * a[0][1]
0