結果

問題 No.1879 How many matchings?
ユーザー yudedakoyudedako
提出日時 2022-04-18 17:08:17
言語 Scala(Beta)
(3.4.0)
結果
AC  
実行時間 999 ms / 2,000 ms
コード長 1,491 bytes
コンパイル時間 12,833 ms
コンパイル使用メモリ 263,956 KB
実行使用メモリ 62,220 KB
最終ジャッジ日時 2023-08-28 13:16:30
合計ジャッジ時間 29,546 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 948 ms
62,024 KB
testcase_01 AC 957 ms
61,884 KB
testcase_02 AC 958 ms
61,868 KB
testcase_03 AC 962 ms
61,864 KB
testcase_04 AC 961 ms
62,172 KB
testcase_05 AC 999 ms
61,880 KB
testcase_06 AC 967 ms
61,744 KB
testcase_07 AC 963 ms
61,792 KB
testcase_08 AC 964 ms
61,944 KB
testcase_09 AC 980 ms
62,220 KB
testcase_10 AC 981 ms
61,996 KB
testcase_11 AC 971 ms
61,904 KB
testcase_12 AC 977 ms
62,080 KB
testcase_13 AC 970 ms
62,108 KB
testcase_14 AC 980 ms
61,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter
import scala.collection.mutable.*
import scala.io.StdIn.*
import scala.util.chaining.*
import scala.math.*
import scala.reflect.ClassTag
import scala.util.*
import scala.annotation.tailrec
import scala.collection.mutable
import scala.language.strictEquality

inline val MOD = 1_000_000_007

class Matrix(val row: Int, val column: Int, val array: Array[Array[Long]]):
  def this(row: Int, column: Int)(generator: (Int, Int) => Long) = this(row, column, Array.tabulate(row){r => Array.tabulate(column){c => generator(r, c)}})
  def *(other: Matrix): Matrix =
    val newRow = row
    val newColumn = other.column
    val mid = column
    Matrix(newRow, newColumn){(i, j) =>
        (0 until mid).foldLeft(0L){(acc, k) => (acc + array(i)(k) * other.array(k)(j)) % MOD}
    }
  def pow(exp: Long): Matrix =
    var result = Matrix.e(row)
    var base = this
    var e = exp
    while e > 0 do
      if (e & 1) == 1 then
        result *= base
      base *= base
      e >>>= 1
    result
  def apply(r: Int, c: Int): Long = array(r)(c)
object Matrix:
  def e(size: Int): Matrix =
    Matrix(size, size) {(i, j) =>
      if i == j then 1
      else 0
    }

@main def main =
  val n = readLine.toLong
  val matrix = Matrix(4, 4, Array[Array[Long]](Array(0, 0, 1, 0), Array(0, 0, 0, 1), Array(1, 0, 1, 0), Array(1, 1, 2, 1)))
  val result = matrix.pow(n / 2) * Matrix(4, 1, Array[Array[Long]](Array(1), Array(1), Array(1), Array(3)))
  println(result((n % 2).toInt, 0))
0