結果

問題 No.1873 Bracket Swapping
コンテスト
ユーザー yudedako
提出日時 2022-03-17 01:31:57
言語 Scala(Beta)
(3.6.2)
結果
TLE  
実行時間 -
コード長 4,606 bytes
コンパイル時間 14,066 ms
コンパイル使用メモリ 272,888 KB
実行使用メモリ 211,100 KB
最終ジャッジ日時 2024-09-25 04:10:40
合計ジャッジ時間 63,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

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

class ModInt(val rawValue: Long) extends AnyVal:
  inline def +(right: ModInt)(using inline mod: Int): ModInt = ModInt((rawValue + right.rawValue) % mod)
  inline def -(right: ModInt)(using inline mod: Int): ModInt = ModInt((rawValue - right.rawValue) % mod)
  inline def *(right: ModInt)(using inline mod: Int): ModInt = ModInt((rawValue * right.rawValue) % mod)
  inline def /(right: ModInt)(using inline mod: Int): ModInt = this * right.inverse
  inline def pow(exp: Long)(using inline mod: Int): ModInt =
    var result = 1L
    var base = rawValue
    var e = exp
    while e > 0 do
      if (e & 1) == 1 then
        result = result * base % mod
      base = base * base % mod
      e >>= 1
    ModInt(result)
  inline def pow(exp: Int)(using inline mod: Int): ModInt = pow(exp.toLong)
  inline def inverse(using inline mod: Int): ModInt =
    var x = rawValue
    var y = mod.toLong
    var a = 1L
    var b = 0L
    var c = 0L
    var d = 1L
    while y != 0 do
      val q = x / y
      val e = a - c * q
      val f = b - d * q
      a = c
      b = d
      c = e
      d = f
      x = y
      y = c * rawValue + d * mod
    require(x.abs == 1L)
    ModInt(if x == 1 then a % mod else -a % mod)
  inline def toLong(using inline mod: Int): Long = (rawValue + mod) % mod
  inline def toInt(using inline mod: Int): Int = ((rawValue + mod) % mod).toInt
  override def toString = rawValue.toString

object ModInt:
  inline def zero: ModInt = ModInt(0)
  inline def one: ModInt = ModInt(1)
  inline given Conversion[Int, ModInt] with
    override def apply(x: Int) = ModInt(x)
  extension (value: Long)
    inline def toModInt(using inline mod: Int): ModInt = ModInt(value % mod)


object Matrix:
  import ModInt.*
  opaque type Matrix = Array[Array[ModInt]]
  extension (array: Array[Array[ModInt]])
    def asMatrix: Matrix = array
  extension (matrix: Matrix)
    def asArray: Array[Array[ModInt]] = matrix
  def E(size: Int): Matrix =
    Array.tabulate(size){i => Array.tabulate(size){j => if i == j then 1 else 0}}
  extension (left: Matrix)
    inline def *(right: Matrix)(using inline mod: Int): Matrix =
      val row = left.length
      val mid = right.length
      val column = right(0).length
      val result = Array.fill(row){Array.fill(column){zero}}
      for
        i <- 0 until row
        j <- 0 until column
      do
        result(i)(j) = (0 until mid).foldLeft(zero){(acc, k) => acc + left(i)(k) * right(k)(j)}
      result
    inline def pow(exp: Int)(using inline mod: Int): Matrix =
      var result = E(left.length)
      var b = left
      var e = exp
      while e > 0 do
        if (e & 1) == 1 then
          result *= b
        b *= b
        e >>= 1
      result
    inline def inspect: String = left.map{_.mkString(", ")}.mkString("\n")

def makeMatrix(size: Int): Matrix.Matrix =
  import Matrix.*
  val half = size / 2
  val result = Array.fill(half + 1){Array.fill(half + 1){ModInt.zero}}
  for
    i <- 0 to half
  do
    if 0 <= i - 1 then
      result(i)(i - 1) = (half - i + 1) * (half - i + 1)
    result(i)(i) = (half - i) * (half - i - 1) + i * (i - 1) + 2 * (size - 2 * i) * i
    if i + 1 <= half then
      result(i)(i + 1) = (i + 1) * (i + 1)
  result.asMatrix

@main def main =
  import ModInt.*
  import Matrix.*
  inline given mod: Int = 998244353
  val str = readLine()
  val k = readLine().toInt
  val size = str.length
  val half = size / 2
  val memo = Array.fill(size + 1){Array.fill(half + 1){Array.fill(half + 1){zero}}}.tap{a => a(0)(0)(0) = one}
  for
    (c, i) <- str.zipWithIndex
    height <- 0 to half
    toRight <- 0 to half
  do
    memo(i + 1)(height)(toRight) = c match
      case '(' =>
        var pattern = zero
        if 0 <= height - 1 then
          pattern += memo(i)(height - 1)(toRight)
        if height + 1 <= half && 0 < toRight then
          pattern += memo(i)(height + 1)(toRight - 1)
        pattern
      case ')' =>
        var pattern = zero
        if height + 1 <= half then
          pattern += memo(i)(height + 1)(toRight)
        if 0 <= height - 1 then
          pattern += memo(i)(height - 1)(toRight)
        pattern
      case _ => ???
  val matrix = makeMatrix(size).pow(k).asArray
  val left = matrix(0)
  val right = memo(size)(0)
  var result = zero
  for toRight <- 0 to half do
    result += left(toRight) * right(toRight)
  println(result.toLong)
0