#1195864 (Scala) No.3310 mod998

• 問題: No.3310 mod998
• ユーザー: phspls
• 提出日時: 2026-10-29 21:15:19
• 言語: Scala (3.10.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 12,839 bytes
• コンパイル時間: 17,332 ms
• コンパイル使用メモリ: 294,064 KB
• 実行使用メモリ: 74,436 KB
• 最終ジャッジ日時: 2026-10-29 21:16:08
• 合計ジャッジ時間: 47,543 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20 TLE * 1 -- * 13

ソースコード

import java.io.{InputStream, OutputStream, IOException, Closeable, Flushable}
import java.nio.charset.StandardCharsets
import scala.annotation.tailrec

// ライブラリ一式
// https://github.com/phspls/scala-kyopro

/**
 * AtCoder向けの高速入出力ライブラリ (Scala Native / Scala 3 双方に対応)
 *
 * 【特徴】
 * 1. Scala Native (LLVM) および Scala 3 (JVM) の両方で追加依存なしにそのまま動作可能
 * 2. 64KB の内部バイトバッファによる低レベル高速読み込み・書き込み
 * 3. 文字列生成・ボクシングを極力排除した整数 (Int/Long) のダイレクトパース & フォーマット
 * 4. AtCoder で頻出する配列入力、複数タプル入力、Yes/No 出力、配列の一括出力などの便利メソッドを完備
 * 5. auto-flush を備えた FastIO.run ユーティリティにより flush 忘れによる WA/TLE を防止
 */
final class FastScanner(private val in: InputStream = System.`in`) {
  private val bufferSize: Int = 1 << 16 // 64 KB
  private val buffer: Array[Byte] = new Array[Byte](bufferSize)
  private var ptr: Int = 0
  private var buflen: Int = 0
  private var tokenBuf: Array[Byte] = new Array[Byte](64)

  @inline private def hasNextByte(): Boolean = {
    if (ptr < buflen) true
    else {
      ptr = 0
      try {
        buflen = in.read(buffer)
      } catch {
        case _: IOException => buflen = -1
      }
      buflen > 0
    }
  }

  @inline private def readByte(): Int = {
    if (hasNextByte()) {
      val b = buffer(ptr) & 0xFF
      ptr += 1
      b
    } else -1
  }

  @inline private def skipWhitespace(): Boolean = {
    while (hasNextByte() && (buffer(ptr) & 0xFF) <= 32) {
      ptr += 1
    }
    hasNextByte()
  }

  /** 次のトークン（空白以外の文字列）が存在するか判定 */
  def hasNext(): Boolean = skipWhitespace()

  /** 次のトークンを String として取得 (UTF-8 対応) */
  def next(): String = {
    if (!skipWhitespace()) throw new java.util.NoSuchElementException("No more tokens in input stream")
    var len = 0
    var b = readByte()
    while (b > 32) {
      if (len == tokenBuf.length) {
        val newBuf = new Array[Byte](tokenBuf.length * 2)
        java.lang.System.arraycopy(tokenBuf, 0, newBuf, 0, len)
        tokenBuf = newBuf
      }
      tokenBuf(len) = b.toByte
      len += 1
      b = readByte()
    }
    new String(tokenBuf, 0, len, StandardCharsets.UTF_8)
  }

  /** 次の 32bit 整数を取得（負数・Int.MinValue 対応） */
  def nextInt(): Int = {
    if (!skipWhitespace()) throw new java.util.NoSuchElementException("No more tokens in input stream")
    var b = readByte()
    var negative = false
    if (b == '-') {
      negative = true
      b = readByte()
    }
    if (b < '0' || b > '9') {
      throw new NumberFormatException(s"Invalid integer character: ${b.toChar}")
    }
    var res = -(b - '0')
    b = readByte()
    while (b >= '0' && b <= '9') {
      res = res * 10 - (b - '0')
      b = readByte()
    }
    if (negative) res else -res
  }

  /** 次の 64bit 整数を取得（負数・Long.MinValue 対応） */
  def nextLong(): Long = {
    if (!skipWhitespace()) throw new java.util.NoSuchElementException("No more tokens in input stream")
    var b = readByte()
    var negative = false
    if (b == '-') {
      negative = true
      b = readByte()
    }
    if (b < '0' || b > '9') {
      throw new NumberFormatException(s"Invalid integer character: ${b.toChar}")
    }
    var res = -(b - '0').toLong
    b = readByte()
    while (b >= '0' && b <= '9') {
      res = res * 10L - (b - '0')
      b = readByte()
    }
    if (negative) res else -res
  }

  /** 次の Double 値を取得 */
  def nextDouble(): Double = java.lang.Double.parseDouble(next())

  /** 次の非空白文字を 1 文字取得 */
  def nextChar(): Char = {
    if (!skipWhitespace()) throw new java.util.NoSuchElementException("No more tokens in input stream")
    readByte().toChar
  }

  /** 改行までの 1 行を取得 */
  def nextLine(): String = {
    if (!hasNextByte()) throw new java.util.NoSuchElementException("No more lines in input stream")
    var len = 0
    var b = readByte()
    while (b != -1 && b != '\n' && b != '\r') {
      if (len == tokenBuf.length) {
        val newBuf = new Array[Byte](tokenBuf.length * 2)
        java.lang.System.arraycopy(tokenBuf, 0, newBuf, 0, len)
        tokenBuf = newBuf
      }
      tokenBuf(len) = b.toByte
      len += 1
      b = readByte()
    }
    if (b == '\r') {
      if (hasNextByte() && (buffer(ptr) & 0xFF) == '\n') {
        ptr += 1
      }
    }
    new String(tokenBuf, 0, len, StandardCharsets.UTF_8)
  }

  // --- 便利メソッド (配列・タプル入力) ---

  def nextIntArray(n: Int): Array[Int] = {
    val arr = new Array[Int](n)
    var i = 0
    while (i < n) {
      arr(i) = nextInt()
      i += 1
    }
    arr
  }

  def nextLongArray(n: Int): Array[Long] = {
    val arr = new Array[Long](n)
    var i = 0
    while (i < n) {
      arr(i) = nextLong()
      i += 1
    }
    arr
  }

  def nextDoubleArray(n: Int): Array[Double] = {
    val arr = new Array[Double](n)
    var i = 0
    while (i < n) {
      arr(i) = nextDouble()
      i += 1
    }
    arr
  }

  def nextStringArray(n: Int): Array[String] = {
    val arr = new Array[String](n)
    var i = 0
    while (i < n) {
      arr(i) = next()
      i += 1
    }
    arr
  }

  def nextInt2(): (Int, Int) = (nextInt(), nextInt())
  def nextInt3(): (Int, Int, Int) = (nextInt(), nextInt(), nextInt())
  def nextInt4(): (Int, Int, Int, Int) = (nextInt(), nextInt(), nextInt(), nextInt())

  def nextLong2(): (Long, Long) = (nextLong(), nextLong())
  def nextLong3(): (Long, Long, Long) = (nextLong(), nextLong(), nextLong())
  def nextLong4(): (Long, Long, Long, Long) = (nextLong(), nextLong(), nextLong(), nextLong())
}

final class FastPrinter(private val out: OutputStream = System.out) extends Closeable with Flushable {
  private val bufferSize: Int = 1 << 16 // 64 KB
  private val buffer: Array[Byte] = new Array[Byte](bufferSize)
  private var ptr: Int = 0
  private val numBuf: Array[Byte] = new Array[Byte](24)

  @inline private def ensureCapacity(needed: Int): Unit = {
    if (ptr + needed > bufferSize) {
      flushBuffer()
    }
  }

  @inline private def flushBuffer(): Unit = {
    if (ptr > 0) {
      out.write(buffer, 0, ptr)
      ptr = 0
    }
  }

  override def flush(): Unit = {
    flushBuffer()
    out.flush()
  }

  override def close(): Unit = {
    flush()
    out.close()
  }

  @inline def print(c: Char): FastPrinter = {
    ensureCapacity(1)
    buffer(ptr) = c.toByte
    ptr += 1
    this
  }

  def print(s: String): FastPrinter = {
    val len = s.length
    var isAscii = true
    var i = 0
    while (i < len && isAscii) {
      if (s.charAt(i) >= 128) isAscii = false
      i += 1
    }
    if (isAscii) {
      i = 0
      while (i < len) {
        val chunk = Math.min(len - i, bufferSize - ptr)
        var j = 0
        while (j < chunk) {
          buffer(ptr + j) = s.charAt(i + j).toByte
          j += 1
        }
        ptr += chunk
        i += chunk
        if (ptr == bufferSize) flushBuffer()
      }
    } else {
      val bytes = s.getBytes(StandardCharsets.UTF_8)
      var off = 0
      while (off < bytes.length) {
        val chunk = Math.min(bytes.length - off, bufferSize - ptr)
        java.lang.System.arraycopy(bytes, off, buffer, ptr, chunk)
        ptr += chunk
        off += chunk
        if (ptr == bufferSize) flushBuffer()
      }
    }
    this
  }

  def print(x: Int): FastPrinter = {
    ensureCapacity(16)
    if (x == 0) {
      buffer(ptr) = '0'.toByte
      ptr += 1
    } else {
      var n = x
      if (n < 0) {
        buffer(ptr) = '-'.toByte
        ptr += 1
        if (n == Int.MinValue) {
          val s = "2147483648"
          var i = 0
          while (i < 10) {
            buffer(ptr) = s.charAt(i).toByte
            ptr += 1
            i += 1
          }
          return this
        }
        n = -n
      }
      var idx = 0
      while (n > 0) {
        numBuf(idx) = ((n % 10) + '0').toByte
        n /= 10
        idx += 1
      }
      while (idx > 0) {
        idx -= 1
        buffer(ptr) = numBuf(idx)
        ptr += 1
      }
    }
    this
  }

  def print(x: Long): FastPrinter = {
    ensureCapacity(24)
    if (x == 0L) {
      buffer(ptr) = '0'.toByte
      ptr += 1
    } else {
      var n = x
      if (n < 0L) {
        buffer(ptr) = '-'.toByte
        ptr += 1
        if (n == Long.MinValue) {
          val s = "9223372036854775808"
          var i = 0
          while (i < 19) {
            buffer(ptr) = s.charAt(i).toByte
            ptr += 1
            i += 1
          }
          return this
        }
        n = -n
      }
      var idx = 0
      while (n > 0L) {
        numBuf(idx) = ((n % 10L) + '0').toByte
        n /= 10L
        idx += 1
      }
      while (idx > 0) {
        idx -= 1
        buffer(ptr) = numBuf(idx)
        ptr += 1
      }
    }
    this
  }

  def print(d: Double): FastPrinter = print(d.toString)

  def print(d: Double, precision: Int): FastPrinter = {
    print(String.format(java.util.Locale.US, s"%.${precision}f", java.lang.Double.valueOf(d)))
  }

  def print(b: Boolean): FastPrinter = print(if (b) "true" else "false")

  @inline def println(): FastPrinter = {
    ensureCapacity(1)
    buffer(ptr) = '\n'.toByte
    ptr += 1
    this
  }

  @inline def println(x: Int): FastPrinter = { print(x); println() }
  @inline def println(x: Long): FastPrinter = { print(x); println() }
  @inline def println(d: Double): FastPrinter = { print(d); println() }
  @inline def println(d: Double, precision: Int): FastPrinter = { print(d, precision); println() }
  @inline def println(s: String): FastPrinter = { print(s); println() }
  @inline def println(c: Char): FastPrinter = { print(c); println() }
  @inline def println(b: Boolean): FastPrinter = { print(b); println() }

  /** AtCoder で頻出する Yes / No 判定出力 */
  @inline def printlnYesNo(cond: Boolean, upper: Boolean = false): FastPrinter = {
    if (upper) {
      println(if (cond) "YES" else "NO")
    } else {
      println(if (cond) "Yes" else "No")
    }
  }

  /** 配列の要素を空白区切りで出力（末尾改行なし） */
  def printArray(arr: Array[Int], sep: String = " "): FastPrinter = {
    var i = 0
    val len = arr.length
    while (i < len) {
      if (i > 0) print(sep)
      print(arr(i))
      i += 1
    }
    this
  }

  /** 配列の要素を空白区切りで出力し、最後に改行 */
  def printlnArray(arr: Array[Int], sep: String = " "): FastPrinter = {
    printArray(arr, sep)
    println()
  }
}


/**
 * 提出用テンプレートの実装例 (Main.scala)
 *   @main
 *   def main(args: Array[String]): Unit = {
 *     val in = new FastScanner()
 *     val out = new FastPrinter()
 *
 *     val n = in.nextInt()
 *     val a = in.nextIntArray(n)
 *     out.println(a.sum)
 *
 *     out.flush() // 最後に必ず flush を呼ぶこと
 *   }
 */

object Main {
  private val in = new FastScanner()
  private val out = new FastPrinter()

  private val MOD = 998

  def main(args: Array[String]): Unit =
    // ----------------------
    // 解法ロジック記述エリア
    // ----------------------
    val t = in.nextInt()
    val result = (0 until t).flatMap(_ => solve()).mkString("\n")
    out.println(result)

    out.flush()

  def solve(): List[Int] =
    val n = in.nextInt()
    val m = in.nextInt()
    val targets = (0 until m).map(_ => BigInt(in.next()))
      
    val iterator = LazyList.iterate(1)(prev => prev * n % MOD)
    val usedAt = loop(Vector.fill(MOD)(None), 0, iterator)
    val endIdx = (0 until MOD).filter(i => usedAt(i).isDefined).maxBy(i => usedAt(i).get)
    val startIdx = endIdx * n % MOD
    val start = usedAt(startIdx).get
    val end = usedAt(endIdx).get

    val firstSum = iterator.take(start).sum
    val secondSums = iterator.drop(start).take(end-start+1).scanLeft(0)((prev, v) => prev + v)
    targets.map(v => {
        if (v+1 < start) {
          iterator.take(v.toInt+1).sum
        } else {
          val rest = v + 1 - start
          val denom = end - start + 1
          val ret = firstSum.toInt
            + (rest / denom % MOD * (secondSums.last % MOD)).toInt 
            + (secondSums((rest % denom).toInt) % MOD).toInt 
          ret % MOD
        }
      })
      .toList


  @tailrec
  def loop(mem: Vector[Option[Int]], counter: Int, stream: LazyList[Int]): Vector[Option[Int]] =
    stream match
      case value #:: tail =>
        mem(value) match
          case None =>
            loop(mem.updated(value, Some(counter)), counter + 1, tail)
          case _ =>
            mem
      case _ =>
        mem
    
}