結果
問題 | No.1620 Substring Sum |
ユーザー | yudedako |
提出日時 | 2022-03-01 16:17:14 |
言語 | Scala(Beta) (3.4.0) |
結果 |
AC
|
実行時間 | 1,278 ms / 2,000 ms |
コード長 | 3,159 bytes |
コンパイル時間 | 15,119 ms |
コンパイル使用メモリ | 258,692 KB |
実行使用メモリ | 70,372 KB |
最終ジャッジ日時 | 2023-09-22 06:03:57 |
合計ジャッジ時間 | 44,060 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 993 ms
61,992 KB |
testcase_01 | AC | 1,007 ms
61,972 KB |
testcase_02 | AC | 1,013 ms
62,928 KB |
testcase_03 | AC | 1,003 ms
62,000 KB |
testcase_04 | AC | 1,248 ms
70,296 KB |
testcase_05 | AC | 1,219 ms
70,068 KB |
testcase_06 | AC | 1,239 ms
70,080 KB |
testcase_07 | AC | 1,252 ms
69,932 KB |
testcase_08 | AC | 1,242 ms
69,816 KB |
testcase_09 | AC | 1,278 ms
70,320 KB |
testcase_10 | AC | 1,252 ms
69,844 KB |
testcase_11 | AC | 1,239 ms
69,900 KB |
testcase_12 | AC | 1,089 ms
64,304 KB |
testcase_13 | AC | 1,235 ms
70,236 KB |
testcase_14 | AC | 1,268 ms
70,372 KB |
testcase_15 | AC | 1,209 ms
66,420 KB |
testcase_16 | AC | 1,249 ms
64,280 KB |
testcase_17 | AC | 1,200 ms
66,200 KB |
testcase_18 | AC | 1,020 ms
62,072 KB |
testcase_19 | AC | 1,003 ms
62,080 KB |
testcase_20 | AC | 1,246 ms
70,300 KB |
testcase_21 | AC | 1,240 ms
70,016 KB |
ソースコード
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 object ModInt: opaque type ModInt = Long inline def zero: ModInt = 0 inline def one: ModInt = 1 extension (value: Long) inline def toModInt(using inline mod: Int): ModInt = value % mod inline def unsafeAsModInt: ModInt = value extension (value: Int) inline def toModInt(using inline mod: Int): ModInt = value % mod inline def unsafeAsModInt: ModInt = value trait Converter[T]: inline def convert(value: T)(using inline mod: Int): ModInt inline given Converter[Int] with override inline def convert(value: Int)(using inline mod: Int) = value.toModInt inline given Converter[Long] with override inline def convert(value: Long)(using inline mod: Int) = value.toModInt inline given Converter[ModInt] with override inline def convert(value: ModInt)(using inline mod: Int) = value extension (modInt: ModInt) inline def value(using inline mod: Int): Long = (modInt + mod) % mod inline def rawValue: Long = modInt inline def inverse(using inline mod: Int): ModInt = var x = modInt 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 * modInt + d * mod require(x.abs == 1L) if x == 1 then a % mod else -a % mod inline def pow(exp: Long)(using inline mod: Int): ModInt = var result = 1L var base = modInt var e = exp while e > 0 do if (e & 1) == 1 then result = result * base % mod base = base * base % mod e >>= 1 result inline def pow(exp: Int)(using inline mod: Int): ModInt = pow(exp.toLong) inline def powMod[B: Converter] (base: B, exp: Int)(using inline mod: Int): ModInt = summon[Converter[B]].convert(base).pow(exp) inline def powMod[B: Converter] (base: B, exp: Long)(using inline mod: Int): ModInt = summon[Converter[B]].convert(base).pow(exp) extension [L: Converter, R: Converter] (left: L) inline def +(right: R)(using inline mod: Int): ModInt = (summon[Converter[L]].convert(left) + summon[Converter[R]].convert(right)).toModInt inline def -(right: R)(using inline mod: Int): ModInt = (summon[Converter[L]].convert(left) - summon[Converter[R]].convert(right)).toModInt inline def *(right: R)(using inline mod: Int): ModInt = (summon[Converter[L]].convert(left) * summon[Converter[R]].convert(right)).toModInt inline def /(right: R)(using inline mod: Int): ModInt = (summon[Converter[L]].convert(left) * summon[Converter[R]].convert(right).inverse).toModInt @main def main = import ModInt.* inline given mod: Int = 998244353 val str = readLine.map(_ - '0') var result = zero for (n, i) <- str.zipWithIndex do result += powMod(2, i) * powMod(11, str.length - i - 1) * n println(result.value)