結果

問題 No.891 隣接3項間の漸化式
ユーザー ikd
提出日時 2019-09-20 22:55:39
言語 Nim
(1.1.1)
結果
AC  
実行時間 4 ms
コード長 799 Byte
コンパイル時間 3,472 ms
使用メモリ 3,136 KB
最終ジャッジ日時 2020-01-28 02:26:34

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample01.txt AC 4 ms
2,908 KB
0_sample02.txt AC 0 ms
2,808 KB
0_sample03.txt AC 4 ms
2,868 KB
1_random_small01.txt AC 0 ms
2,872 KB
1_random_small02.txt AC 4 ms
2,892 KB
1_random_small03.txt AC 0 ms
2,952 KB
1_random_small04.txt AC 0 ms
3,132 KB
1_random_small05.txt AC 4 ms
2,872 KB
1_random_small06.txt AC 0 ms
2,912 KB
1_random_small07.txt AC 4 ms
2,916 KB
1_random_small08.txt AC 0 ms
2,928 KB
1_random_small09.txt AC 4 ms
3,080 KB
1_random_small10.txt AC 0 ms
2,892 KB
2_corner01.txt AC 4 ms
2,844 KB
2_corner02.txt AC 0 ms
2,900 KB
2_corner03.txt AC 4 ms
3,136 KB
2_corner04.txt AC 4 ms
2,896 KB
2_corner05.txt AC 0 ms
2,876 KB
2_corner06.txt AC 4 ms
3,116 KB
2_corner07.txt AC 0 ms
3,136 KB
2_corner08.txt AC 4 ms
2,900 KB
2_corner09.txt AC 0 ms
2,936 KB
2_corner10.txt AC 0 ms
2,896 KB
2_corner11.txt AC 4 ms
2,940 KB
2_corner12.txt AC 0 ms
2,900 KB
3_random01.txt AC 4 ms
2,952 KB
3_random02.txt AC 0 ms
3,080 KB
3_random03.txt AC 0 ms
2,912 KB
3_random04.txt AC 4 ms
2,872 KB
3_random05.txt AC 0 ms
2,904 KB
3_random06.txt AC 4 ms
2,912 KB
3_random07.txt AC 0 ms
2,836 KB
3_random08.txt AC 4 ms
2,808 KB
3_random09.txt AC 0 ms
2,956 KB
3_random10.txt AC 0 ms
2,924 KB
4_large01.txt AC 4 ms
2,956 KB
4_large02.txt AC 0 ms
2,812 KB
4_large03.txt AC 4 ms
2,908 KB
4_large04.txt AC 0 ms
2,836 KB
4_large05.txt AC 4 ms
2,868 KB
4_large06.txt AC 0 ms
2,912 KB
4_large07.txt AC 4 ms
3,136 KB
テストケース一括ダウンロード
コンパイルメッセージ
CC: stdlib_io.nim
CC: stdlib_system.nim
CC: stdlib_parseutils.nim
CC: stdlib_strutils.nim
CC: stdlib_sequtils.nim
CC: Main.nim

ソースコード

diff #
import strutils, sequtils

const mo: int64 = 1000000000 + 7
proc add(a: var int64, b: int64) =
  a = (a + b) mod mo

proc main() =
  var a, b, n: int
  (a, b, n) = stdin.readLine.strip.split.map(parseInt)

  if n <= 1:
    echo n
    return
  var mat = newSeqWith(32, newSeqwith(2, newSeq[int64](2)))
  mat[0][0][0] = a
  mat[0][0][1] = b
  mat[0][1][0] = 1
  mat[0][1][1] = 0
  for i in 1..<32:
    for y in 0..<2:
      for x in 0..<2:
        for t in 0..<2:
          add(mat[i][y][x], mat[i - 1][y][t] * mat[i - 1][t][x] mod mo)
  var v = newSeq[int64](2)
  v[0] = 1
  v[1] = 0
  for i in 0..<32:
    if ((n - 1) and (1 shl i)) > 0:
      var u = newSeq[int64](2)
      for j in 0..<2:
        for t in 0..<2:
          add(u[j], mat[i][j][t] * v[t] mod mo)
      swap(u, v)
  echo v[0]
main()
0