結果

問題 No.1073 無限すごろく
コンテスト
ユーザー Haar
提出日時 2020-06-16 16:23:49
言語 Nim
(2.2.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,207 bytes
コンパイル時間 3,541 ms
コンパイル使用メモリ 64,932 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-03 11:53:56
合計ジャッジ時間 4,198 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils

type
  ModInt*[M: static[int]] = distinct int64

proc `+`*[M](lhs, rhs: ModInt[M]): ModInt[M] {.noSideEffect.} =
  var t = int64(lhs) + int64(rhs)
  if t >= M: t -= M
  return ModInt[M](t)

proc `+`*[M](lhs: ModInt[M], rhs: int64): ModInt[M] {.noSideEffect.} =
  return ModInt[M]((int64(lhs) + rhs mod M) mod M)

proc `-`*[M](lhs, rhs: ModInt[M]): ModInt[M] {.noSideEffect.} =
  var t = int64(lhs) - int64(rhs)
  if t < 0: t += M
  return ModInt[M](t)

proc `-`*[M](lhs: ModInt[M], rhs: int64): ModInt[M] {.noSideEffect.} =
  var t = int64(lhs) - rhs mod M
  if t < 0: t += M
  return ModInt[M](t)

proc `*`*[M](lhs, rhs: ModInt[M]): ModInt[M] {.noSideEffect.} = return ModInt[M]((int64(lhs) * int64(rhs)) mod M)
proc `*`*[M](lhs: ModInt[M], rhs: int64): ModInt[M] {.noSideEffect.} = return ModInt[M]((int64(lhs) * rhs mod M) mod M)

proc pow*[M](a: ModInt[M], p: int64): ModInt[M] {.noSideEffect.} =
  var
    ret = ModInt[M](1)
    a = a
    p = p

  while p > 0:
    if (p and 1) == 1: ret = ret * a
    a = a * a
    p = p shr 1

  return ret


proc inv*[M](a: ModInt[M]): ModInt[M] {.noSideEffect.} =
  var
    a: int64 = int64(a)
    b: int64 = M
    u: int64 = 1
    v: int64 = 0

  while b != 0:
    let t = a div b
    a -= t * b
    swap(a, b)
    u -= t * v
    swap(u, v)

  u = u mod M
  if u < 0: u += M

  return ModInt[M](u)

proc `/`*[M](lhs, rhs: ModInt[M]): ModInt[M] {.noSideEffect.} = return lhs * rhs.inv

proc frac*[M](x: typedesc[ModInt[M]], a: int64, b: int64): ModInt[M] {.noSideEffect.} = return ModInt[M](a) * ModInt[M](b).inv
proc new*[M](x: typedesc[ModInt[M]], a: int64): ModInt[M] {.noSideEffect.} = return ModInt[M](a)

proc `$`*[M](a: ModInt[M]): string {.noSideEffect.} = $(int64(a))
proc `+=`*[M](lhs: var ModInt[M], rhs: ModInt[M]) = lhs = lhs + rhs
proc `-=`*[M](lhs: var ModInt[M], rhs: ModInt[M]) = lhs = lhs - rhs
proc `*=`*[M](lhs: var ModInt[M], rhs: ModInt[M]) = lhs = lhs * rhs
proc `/=`*[M](lhs: var ModInt[M], rhs: ModInt[M]) = lhs = lhs / rhs

proc zero*[M](t: type[ModInt[M]]): ModInt[M] {.noSideEffect.} = return ModInt[M](0)
proc one*[M](t: type[ModInt[M]]): ModInt[M] {.noSideEffect.} = return ModInt[M](1)


type
  Matrix*[T; N: static[int]] = array[0 .. N-1, array[0 .. N-1, T]]

proc zero*[T, N](t: type[Matrix[T, N]]): Matrix[T, N] {.noSideEffect.} =
  var ret: Matrix[T, N]
  return ret

proc one*[T, N](t: type[Matrix[T, N]]): Matrix[T, N] {.noSideEffect.} =
  var ret: Matrix[T, N]
  for i in 0 ..< N: ret[i][i] = T.one
  return ret

proc `*`*[T, N](lhs: Matrix[T, N], rhs: Matrix[T, N]): Matrix[T, N] {.noSideEffect.} =
  var ret: Matrix[T, N]
  for i in 0 ..< N:
    for j in 0 ..< N:
      for k in 0 ..< N:
        ret[i][j] += lhs[i][k] * rhs[k][j]
  return ret

proc pow*[T, N](a: Matrix[T, N], p: int64): Matrix[T, N] {.noSideEffect.} =
  var
    ret = Matrix[T, N].one()
    a = a
    p = p

  while p > 0:
    if (p and 1) == 1: ret = ret * a
    a = a * a
    p = p div 2

  return ret


type mint = ModInt[1000000007]
type mat = Matrix[mint, 6]

let N = parseInt(readline(stdin))

var m = mat.zero();

for i in 0 ..< 6:
  m[0][i] = mint.frac(1, 6)

for i in 1 ..< 6:
  m[i][i-1] = mint.new(1)

m = m.pow(N)
echo m[0][0]
0