結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-05-02 07:19:01
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,032 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 66,964 KB
最終ジャッジ日時 2024-11-14 19:02:50
合計ジャッジ時間 1,594 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(14, 16) Error: type mismatch
Expression: <len(a)
  [1] len(a): int

Expected one of (first mismatch at [position]):
[1] proc `<`(x, y: bool): bool
[1] proc `<`(x, y: char): bool
[1] proc `<`(x, y: float): bool
[1] proc `<`(x, y: float32): bool
[1] proc `<`(x, y: int16): bool
[1] proc `<`(x, y: int32): bool
[1] proc `<`(x, y: int8): bool
[1] proc `<`(x, y: pointer): bool
[1] proc `<`(x, y: string): bool
[1] proc `<`(x, y: uint): bool
[1] proc `<`(x, y: uint16): bool
[1] proc `<`(x, y: uint32): bool
[1] proc `<`(x, y: uint64): bool
[1] proc `<`(x, y: uint8): bool
[1] proc `<`[Enum: enum](x, y: Enum): bool
[1] proc `<`[T: tuple](x, y: T): bool
[1] proc `<`[T](x, y: ptr T): bool
[1] proc `<`[T](x, y: ref T): bool
[1] proc `<`[T](x, y: set[T]): bool
[2] proc `<`(x, y: int): bool
[2] proc `<`(x, y: int64): bool

ソースコード

diff # 

import strutils, sequtils

const MOD = int(1e9 + 7)

proc `%%`(a: int64, b: int64): int64 = result = (a + b) mod b
template `+%=` (a, b: int64) = a = (a + b) mod MOD
#template `-%=` (a, b: int64) = a = (a - b) mod MOD
template `+%%=` (a, b: int64) = a = (a + b) %% MOD
template `-%%=` (a, b: int64) = a = (a - b + MOD) %% MOD

proc matmul(a: seq[seq[int64]], b: seq[seq[int64]]): seq[seq[int64]] =
  var (a, b) = (a, b)
  result = newSeqWith(a.len, newSeq[int64](b[0].len))
  for i in 0.. <a.len:
    for k in 0.. <b.len:
      for j in 0.. <b[0].len:
         result[i][j] +%%= (a[i][k] * b[k][j])

proc matpow(a: var seq[seq[int64]], n: var int64): seq[seq[int64]] =
  result = newSeqWith(a.len, newSeq[int64](a.len))
  for i in 0.. <a.len:
    for j in 0.. <a.len:
      result[i][j] = if i==j: 1 else: 0
  while n > 0:
    if (n and 1) == 1: result = matmul(result, a)
    a = matmul(a, a)
    n = n shr 1

proc solve1(n: int, k: int, a: seq[int]): tuple[a: int, b: int] =
  var (k, n, a) = (k, n, a)
  var y = 0
  for i in 0.. <n:
    y +%= a[i]
  var z = y
  for i in n.. <k:
    a.add(z)
    y +%= z
#    z +%= z
#    z -%%= a[i-n]
    z = (z + z - a[i-n] + MOD) %% MOD
  result = (a[a.len-1], y)

proc solve2(n: int, k: int64, a: seq[int]): tuple[a: int, b: int] =
  var (k, n, a) = (k, n, a)
  var s = newSeqWith(n+1, newSeq[int64](1))
  s[n][0] = 0
  s[n-1][0] = a[0]
  for i in 1.. <n: s[n-1-i][0] = s[n-i][0] + a[i]
  var mat = newSeqWith(n+1, newSeq[int64](n+1))
  mat[0][0] = 2
  mat[0][n] = -1
  for i in 0.. <n: mat[i+1][i] = 1
  var times: int64 = k-n
  var powered = matpow(mat, times)
  var res     = matmul(powered, s)
  var x = res[0][0]
  var y = res[1][0]
  result = (int((x-y) %% MOD), int(x))

var
  scan = stdin.readLine.split.map(parseInt)
  n: int = scan[0]
  k: int64 = scan[1]
  a = newSeq[int](n)
scan = stdin.readLine.split.map(parseInt)
for i in 0.. <n: a[i] = scan[i]
var res: tuple[a: int, b: int]
if k <= int(1e6):
  res = solve1(n, int(k), a)
else:
  res = solve2(n, k, a)
echo res.a, " ", res.b
0