結果

問題 No.1073 無限すごろく
ユーザー HaarHaar
提出日時 2020-06-16 16:23:49
言語 Nim
(2.0.2)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,207 bytes
コンパイル時間 3,953 ms
コンパイル使用メモリ 68,348 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-16 11:02:06
合計ジャッジ時間 5,814 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 1 ms
4,384 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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