結果

問題 No.1879 How many matchings?
ユーザー yudedakoyudedako
提出日時 2022-04-18 17:08:17
言語 Scala(Beta)
(3.4.0)
結果
AC  
実行時間 979 ms / 2,000 ms
コード長 1,491 bytes
コンパイル時間 12,874 ms
コンパイル使用メモリ 266,988 KB
実行使用メモリ 63,520 KB
最終ジャッジ日時 2024-06-09 08:35:56
合計ジャッジ時間 28,543 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 916 ms
63,352 KB
testcase_01 AC 911 ms
63,260 KB
testcase_02 AC 911 ms
63,152 KB
testcase_03 AC 914 ms
63,268 KB
testcase_04 AC 920 ms
63,280 KB
testcase_05 AC 915 ms
63,072 KB
testcase_06 AC 924 ms
63,052 KB
testcase_07 AC 916 ms
63,032 KB
testcase_08 AC 914 ms
63,520 KB
testcase_09 AC 952 ms
63,264 KB
testcase_10 AC 933 ms
63,384 KB
testcase_11 AC 938 ms
63,092 KB
testcase_12 AC 979 ms
63,100 KB
testcase_13 AC 942 ms
63,392 KB
testcase_14 AC 941 ms
63,332 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