結果

問題 No.1879 How many matchings?
コンテスト
ユーザー yudedako
提出日時 2022-04-18 17:08:17
言語 Scala(Beta)
(3.6.2)
結果
AC  
実行時間 1,012 ms / 2,000 ms
コード長 1,491 bytes
コンパイル時間 13,725 ms
コンパイル使用メモリ 266,448 KB
実行使用メモリ 65,260 KB
最終ジャッジ日時 2024-12-29 13:04:17
合計ジャッジ時間 30,212 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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