結果
| 問題 | No.1300 Sum of Inversions |
| ユーザー |
 da_louis
|
| 提出日時 | 2020-11-28 20:19:52 |
| 言語 | Kotlin (1.9.23) |
| 結果 |
AC
|
| 実行時間 | 922 ms / 2,000 ms |
| コード長 | 32,852 bytes |
| コンパイル時間 | 24,908 ms |
| コンパイル使用メモリ | 504,928 KB |
| 実行使用メモリ | 109,024 KB |
| 最終ジャッジ日時 | 2024-04-27 03:34:05 |
| 合計ジャッジ時間 | 52,227 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 281 ms
62,432 KB |
| testcase_01 | AC | 284 ms
62,428 KB |
| testcase_02 | AC | 283 ms
62,404 KB |
| testcase_03 | AC | 922 ms
103,008 KB |
| testcase_04 | AC | 809 ms
102,832 KB |
| testcase_05 | AC | 712 ms
100,684 KB |
| testcase_06 | AC | 835 ms
106,824 KB |
| testcase_07 | AC | 806 ms
104,940 KB |
| testcase_08 | AC | 799 ms
106,836 KB |
| testcase_09 | AC | 815 ms
106,916 KB |
| testcase_10 | AC | 633 ms
87,856 KB |
| testcase_11 | AC | 666 ms
87,512 KB |
| testcase_12 | AC | 768 ms
102,752 KB |
| testcase_13 | AC | 754 ms
102,808 KB |
| testcase_14 | AC | 800 ms
109,024 KB |
| testcase_15 | AC | 883 ms
106,764 KB |
| testcase_16 | AC | 819 ms
102,864 KB |
| testcase_17 | AC | 617 ms
87,432 KB |
| testcase_18 | AC | 698 ms
100,696 KB |
| testcase_19 | AC | 677 ms
100,556 KB |
| testcase_20 | AC | 745 ms
103,380 KB |
| testcase_21 | AC | 773 ms
102,764 KB |
| testcase_22 | AC | 693 ms
100,752 KB |
| testcase_23 | AC | 777 ms
107,012 KB |
| testcase_24 | AC | 694 ms
100,668 KB |
| testcase_25 | AC | 656 ms
91,692 KB |
| testcase_26 | AC | 676 ms
89,864 KB |
| testcase_27 | AC | 623 ms
100,608 KB |
| testcase_28 | AC | 803 ms
106,752 KB |
| testcase_29 | AC | 776 ms
100,700 KB |
| testcase_30 | AC | 815 ms
106,920 KB |
| testcase_31 | AC | 701 ms
100,952 KB |
| testcase_32 | AC | 701 ms
101,048 KB |
| testcase_33 | AC | 486 ms
102,668 KB |
| testcase_34 | AC | 497 ms
108,612 KB |
| testcase_35 | AC | 491 ms
108,776 KB |
| testcase_36 | AC | 504 ms
108,864 KB |
コンパイルメッセージ
Main.kt:125:13: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
appendln(n)
^
Main.kt:214:48: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:214:62: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:215:68: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
^
Main.kt:247:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:273:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:279:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '.'.toByte()) {
^
ソースコード
import java.io.ByteArrayInputStream
import java.io.ByteArrayOutputStream
import java.io.PrintStream
import java.util.*
fun main() = if (localEnv && execChecker) checker() else contest276c()
fun contest276c() = solve()
@OptIn(ExperimentalStdlibApi::class)
private fun solve() = Messiah_contest276c(MOD).exec {
val n = readInt()
val aList = readLong(n)
val bList = aList.withIndex().sortedBy { it.value }
val s = FenwickTree(n + 1)
val v = FenwickTree(n + 1)
val t = FenwickTree(n + 1)
val u = FenwickTree(n + 1)
var answer = Messiah_contest276c.Mint.ZERO
repeat(n) {
val (index, value) = bList[it]
val count = s.sum(index, n)
val sum1 = t.sum(index, n)
val sum2 = u.sum(index, n)
val count2 = v.sum(index, n)
s.add(index, 1)
t.add(index, value)
u.add(index, (sum1.toMint() + count * value).toLong())
v.add(index, count)
answer += sum2.toMint() + count2 * value
}
println(answer)
}
/**
* Fenwick tree(0-indexed).
*
* convert from [AtCoderLibraryForJava - FenwickTree](https://github.com/NASU41/AtCoderLibraryForJava/blob/b0702e6e27f0e2df657df55231a2441c506db5a6/FenwickTree/FenwickTree.java)
*/
private class FenwickTree(private val n: Int) {
private val data: LongArray = LongArray(n)
/**
* Fenwick tree constructor.
*/
constructor(data: LongArray) : this(data.size) {
build(data)
}
/**
* Add value x to p.
*/
fun add(p: Int, x: Long) {
var vp = p
assert(vp in 0 until n)
vp++
while (vp <= n) {
data[vp - 1] += x
vp += vp and -vp
}
}
/**
* Calc sum [l, r].
*/
fun sum(l: Int, r: Int): Long {
assert(l in 0..r && r <= n)
return sum(r) - sum(l)
}
private fun sum(r: Int): Long {
var vr = r
var s: Long = 0
while (vr > 0) {
s += data[vr - 1]
s %= MOD
vr -= vr and -vr
}
return s
}
private fun build(dat: LongArray) {
System.arraycopy(dat, 0, data, 0, n)
for (i in 1..n) {
val p = i + (i and -i)
if (p <= n) {
data[p - 1] += data[i - 1]
}
}
}
}
private const val MOD = 998244353
// region kokokara template dayo (^o^)
private const val execChecker = false
private val localEnv = "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv()
private fun checker() = Messiah_contest276c(MOD).exec {
debugln("#######################################################")
debugln("############### executing check mode. ###############")
debugln("#######################################################")
fun getOutPut(input: String, action: () -> Unit): String {
System.setIn(ByteArrayInputStream(input.toByteArray()))
val sysOut = ByteArrayOutputStream()
System.setOut(PrintStream(sysOut))
action()
return sysOut.toString()
}
val wrongCases = mutableSetOf<List<String>>()
while (wrongCases.size < 10) {
/*
examples
val randomString = (1..20).map { ('a'..'z').random() }.joinToString("")
val randomNum = Random.nextInt(0,2000)
*/
val n = 0
val input = buildString {
appendln(n)
}
val solve = getOutPut(input, ::solve)
val greedy = getOutPut(input, ::greedy)
if (solve != greedy && wrongCases.add(listOf(solve, greedy))) {
debugln("#################### wrong case: ${wrongCases.size} ####################")
debugln("input:")
debugln(input)
debugln("solve:")
debugln(solve)
debugln("greedy:")
debugln(greedy)
}
}
}
private fun greedy() = Messiah_contest276c(MOD).exec {
TODO()
}
@Suppress("ClassName", "unused", "FunctionName", "PropertyName")
private class Messiah_contest276c(mod: Int) {
fun Long.toMint() = Mint(this)
fun Int.toMint() = Mint(this.toLong())
/**
* ModInt. you know, right?
* TODO add test case
*/
@Suppress("unused")
class Mint(value: Long) {
constructor(other: Mint) : this(other.value)
private val value = (value % MOD).let { if (it < 0) it + MOD else it }
operator fun unaryPlus() = this
operator fun unaryMinus() = Mint(MOD - this.value)
operator fun inc() = this.plus(1)
operator fun dec() = this.minus(1)
operator fun plus(other: Long) = Mint(this.value + other)
operator fun plus(other: Mint) = this.plus(other.value)
operator fun minus(other: Long) = Mint(this.value - other)
operator fun minus(other: Mint) = this.plus(-other)
operator fun times(other: Long) = Mint(this.value * Mint(other).value)
operator fun times(other: Mint) = this.times(other.value)
operator fun div(other: Long) = this.times(modPow(other, MOD - 2L))
operator fun div(other: Mint) = this.div(other.value)
fun mod(mod: Long) = Mint(this.value % mod)
fun pow(other: Long) = Mint(modPow(this.value, other))
fun toLong() = this.value
override fun toString() = this.value.toString()
override fun hashCode() = value.hashCode()
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (javaClass != other?.javaClass) return false
other as Mint
return value == other.value
}
companion object {
val ZERO = Mint(0)
val ONE = Mint(1)
val TWO = Mint(2)
val TEN = Mint(10)
private fun modPow(n: Long, p: Long): Long {
var x = n % MOD
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % MOD
y = y shr 1
x = (x * x) % MOD
}
return result
}
}
}
//////////////////////////////////////////////////
// IO
//////////////////////////////////////////////////
private val input = System.`in`
private val buffer = ByteArray(1024)
private var pointer = 0
private var bufferLength = 0
private val sb = StringBuilder()
private fun Byte.isPrintable() = this in 33..126
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
private val lineSeparator: String = System.lineSeparator()
private fun hasNextByte(): Boolean {
return if (pointer < bufferLength) true else {
pointer = 0
bufferLength = input.read(buffer)
bufferLength > 0
}
}
private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit
fun readString(): String {
hasNextOrError()
val sb = StringBuilder()
var b = readByte()
while (b.isPrintable()) {
sb.appendCodePoint(b.toInt())
b = readByte()
}
return sb.toString()
}
fun readLong(): Long {
hasNextOrError()
var n = 0L
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
if (!b.isNumeric()) error("$b is not numeric.")
while (true) {
when {
b.isNumeric() -> n = n * 10 + b.toNumVal()
b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
else -> error("failed to parse. [n=$n, b=$b]")
}
b = readByte()
}
}
fun readInt() = readLong()
.let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }
fun readIntAsIndex() = readInt().dec()
fun readDouble(): Double {
hasNextOrError()
var n = 0.0
var div = 1.0
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
do n = n * 10 + b.toNumVal()
while (run { b = readByte() }.run { b.isNumeric() })
if (b == '.'.toByte()) {
while (run { b = readByte() }.run { b.isNumeric() })
n += b.toNumVal() / (run { div *= 10 }.run { div })
}
return if (negative) -n else n
}
fun readString(size: Int): Array<String> = Array(size) { readString() }
@Suppress("UNUSED_PARAMETER")
fun readChars(h: Int, w: Int): Array<CharArray> = Array(h) { readString().toCharArray() }
fun readLong(size: Int): LongArray = LongArray(size) { readLong() }
fun readLong(h: Int, w: Int): Array<LongArray> = Array(h) { readLong(w) }
fun readInt(size: Int): IntArray = IntArray(size) { readInt() }
fun readInt(h: Int, w: Int): Array<IntArray> = Array(h) { readInt(w) }
fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() }
fun readIntAsIndex(h: Int, w: Int): Array<IntArray> = Array(h) { readIntAsIndex(w) }
fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() }
fun readDouble(h: Int, w: Int): Array<DoubleArray> = Array(h) { readDouble(w) }
fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray =
BooleanArray(size) { readString() == trueElement }
fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array<BooleanArray> =
Array(h) { readBooleanWithSeparator(w, trueElement) }
@Suppress("UNUSED_PARAMETER")
fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray =
readString().map { it == trueElement }.toBooleanArray()
fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array<BooleanArray> =
Array(h) { readBooleanWithoutSeparator(w, trueElement) }
fun println(): Unit = run { sb.append(lineSeparator) }
fun print(any: Any): Unit = run { sb.append(any.toString()) }
fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) }
fun flush() = run { kotlin.io.println(sb); sb.clear() }
fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) }
fun debugln(): Unit = run { if (localEnv) System.err.println() }
fun debugln(action: () -> Unit): Unit = run { if (localEnv) action() }
fun exec(action: Messiah_contest276c.() -> Unit) {
var t: Throwable? = null
Thread(null, { action() }, "sandbox.test.solve", 128 * 1024 * 1024)
.apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
.apply { start() }.join()
t?.let { throw it }
kotlin.io.print(sb)
}
fun readLine(): Nothing = error("readLine is disabled.")
//////////////////////////////////////////////////
// Mod
//////////////////////////////////////////////////
class ModIntFactory(private val mod: Int) {
private val ma = ModArithmetic.of(mod)
/**
* ModInt を生成する.
* 生成された ModInt は、[value] をファクトリ生成時に指定した mod で割った余りを持つ.
*/
fun create(value: Long): ModInt {
val v = (value % mod).let { if (it < 0) it + mod else it }
return if (ma is ModArithmetic.ModArithmeticMontgomery) {
ModInt(ma.generate(v))
} else {
ModInt(v.toInt())
}
}
inner class ModInt(private var rawValue: Int) {
val mod = this@ModIntFactory.mod
val value: Int
get() = if (ma is ModArithmetic.ModArithmeticMontgomery) {
ma.reduce(rawValue.toLong())
} else {
rawValue
}
operator fun plus(mi: ModInt) = ModInt(ma.add(rawValue, mi.rawValue))
operator fun minus(mi: ModInt) = ModInt(ma.sub(rawValue, mi.rawValue))
operator fun times(mi: ModInt) = ModInt(ma.mul(rawValue, mi.rawValue))
operator fun div(mi: ModInt) = ModInt(ma.div(rawValue, mi.rawValue))
/** (this * inv) % mod = 1 を満たすような inv を ModInt として生成して返す. */
fun inv() = ModInt(ma.inv(rawValue))
/** (this ^ [b]) % mod の結果を ModInt として生成して返す. */
fun pow(b: Long) = ModInt(ma.pow(rawValue, b))
/** this を this + [mi] に変更する */
fun addAsg(mi: ModInt): ModInt {
rawValue = ma.add(rawValue, mi.rawValue)
return this
}
/** this を this - [mi] に変更する */
fun subAsg(mi: ModInt): ModInt {
rawValue = ma.sub(rawValue, mi.rawValue)
return this
}
/** this を this * [mi] に変更する */
fun mulAsg(mi: ModInt): ModInt {
rawValue = ma.mul(rawValue, mi.rawValue)
return this
}
/** this を this / [mi] に変更する */
fun divAsg(mi: ModInt): ModInt {
rawValue = ma.div(rawValue, mi.rawValue)
return this
}
override fun toString(): String {
return value.toString()
}
override fun equals(other: Any?): Boolean {
if (other is ModInt) {
return mod == other.mod && value == other.value
}
return false
}
override fun hashCode(): Int {
return (1 * 37 + mod) * 37 + value
}
}
internal interface ModArithmetic {
fun mod(): Int
fun add(a: Int, b: Int): Int
fun sub(a: Int, b: Int): Int
fun mul(a: Int, b: Int): Int
fun div(a: Int, b: Int): Int {
return mul(a, inv(b))
}
fun inv(a: Int): Int
fun pow(a: Int, b: Long): Int
class ModArithmetic1 : ModArithmetic {
override fun mod(): Int {
return 1
}
override fun add(a: Int, b: Int): Int {
return 0
}
override fun sub(a: Int, b: Int): Int {
return 0
}
override fun mul(a: Int, b: Int): Int {
return 0
}
override fun inv(a: Int): Int {
throw ArithmeticException("divide by zero")
}
override fun pow(a: Int, b: Long): Int {
return 0
}
}
class ModArithmetic2 : ModArithmetic {
override fun mod(): Int {
return 2
}
override fun add(a: Int, b: Int): Int {
return a xor b
}
override fun sub(a: Int, b: Int): Int {
return a xor b
}
override fun mul(a: Int, b: Int): Int {
return a and b
}
override fun inv(a: Int): Int {
if (a == 0) throw ArithmeticException("divide by zero")
return a
}
override fun pow(a: Int, b: Long): Int {
return if (b == 0L) 1 else a
}
}
class ModArithmetic998244353 : ModArithmetic {
private val mod = 998244353
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val res = a + b
return if (res >= mod) res - mod else res
}
override fun sub(a: Int, b: Int): Int {
val res = a - b
return if (res < 0) res + mod else res
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res: Long = 1
var pow2 = a.toLong()
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = pow2 * pow2 % mod
idx = idx shl 1
}
res = res * pow2 % mod
vb = vb xor lsb
}
return res.toInt()
}
}
class ModArithmetic1000000007 : ModArithmetic {
private val mod = 1000000007
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val res = a + b
return if (res >= mod) res - mod else res
}
override fun sub(a: Int, b: Int): Int {
val res = a - b
return if (res < 0) res + mod else res
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun div(a: Int, b: Int): Int {
return mul(a, inv(b))
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res: Long = 1
var pow2 = a.toLong()
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = pow2 * pow2 % mod
idx = idx shl 1
}
res = res * pow2 % mod
vb = vb xor lsb
}
return res.toInt()
}
}
class ModArithmeticMontgomery(mod: Int) : ModArithmeticDynamic(mod) {
private val negInv: Long
private val r2: Long
private val r3: Long
fun generate(x: Long): Int {
return reduce(x * r2)
}
fun reduce(x: Long): Int {
var vx = x
vx = vx + (vx * negInv and 0xffffffffL) * mod ushr 32
return (if (vx < mod) vx else vx - mod).toInt()
}
override fun mul(a: Int, b: Int): Int {
return reduce(a.toLong() * b)
}
override fun inv(a: Int): Int {
var va = a
va = super.inv(va)
return reduce(va * r3)
}
override fun pow(a: Int, b: Long): Int {
return generate(super.pow(a, b).toLong())
}
init {
var inv: Long = 0
var s: Long = 1
var t: Long = 0
for (i in 0..31) {
if (t and 1 == 0L) {
t += mod.toLong()
inv += s
}
t = t shr 1
s = s shl 1
}
val r = (1L shl 32) % mod
negInv = inv
r2 = r * r % mod
r3 = r2 * r % mod
}
}
class ModArithmeticBarrett(mod: Int) : ModArithmeticDynamic(mod) {
private val mh: Long
private val ml: Long
private fun reduce(x: Long): Int {
var vx = x
var z = (vx and mask) * ml
z = (vx and mask) * mh + (vx ushr 32) * ml + (z ushr 32)
z = (vx ushr 32) * mh + (z ushr 32)
vx -= z * mod
return (if (vx < mod) vx else vx - mod).toInt()
}
override fun mul(a: Int, b: Int): Int {
return reduce(a.toLong() * b)
}
companion object {
private const val mask = 0xffffffffL
}
init {
/**
* m = floor(2^64/mod)
* 2^64 = p*mod + q, 2^32 = a*mod + b
* => (a*mod + b)^2 = p*mod + q
* => p = mod*a^2 + 2ab + floor(b^2/mod)
*/
val a = (1L shl 32) / mod
val b = (1L shl 32) % mod
val m = a * a * mod + 2 * a * b + b * b / mod
mh = m ushr 32
ml = m and mask
}
}
open class ModArithmeticDynamic(val mod: Int) : ModArithmetic {
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val sum = a + b
return if (sum >= mod) sum - mod else sum
}
override fun sub(a: Int, b: Int): Int {
val sum = a - b
return if (sum < 0) sum + mod else sum
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res = 1
var pow2 = a
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = mul(pow2, pow2)
idx = idx shl 1
}
res = mul(res, pow2)
vb = vb xor lsb
}
return res
}
}
companion object {
fun of(mod: Int): ModArithmetic {
return when {
mod <= 0 -> throw IllegalArgumentException()
mod == 1 -> ModArithmetic1()
mod == 2 -> ModArithmetic2()
mod == 998244353 -> ModArithmetic998244353()
mod == 1000000007 -> ModArithmetic1000000007()
mod and 1 == 1 -> ModArithmeticMontgomery(mod)
else -> ModArithmeticBarrett(mod)
}
}
}
}
}
val modArithmetic = ModIntFactory.ModArithmetic.of(mod)
fun Int.plusMod(b: Int): Int = modArithmetic.add(this, b)
fun Int.minusMod(b: Int): Int = modArithmetic.sub(this, b)
fun Int.timesMod(b: Int): Int = modArithmetic.mul(this, b)
fun Int.divMod(b: Int): Int = modArithmetic.div(this, b)
fun Int.invMod(): Int = modArithmetic.inv(this)
fun Int.powMod(b: Long): Int = modArithmetic.pow(this, b)
val mod: Int get() = modArithmetic.mod()
//////////////////////////////////////////////////
// Misc
//////////////////////////////////////////////////
/**
* `n.indices()` is sugar syntax of `0 until n`.
*/
val Int.indices: IntRange get() = 0 until this
/**
* `[index] in [this]` is sugar syntax of `index in 0 until [this]`.
*/
operator fun Int.contains(index: Int): Boolean = index in this.indices
/**
* `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun <R> Int.mapIndices(transform: (Int) -> R): List<R> = this.indices.map(transform)
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.mapIndices(x: Int, transform: (Int, Int) -> R): List<List<R>> =
this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List<R> =
this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform)
/**
* `[this].forEachIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit =
this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } }
/**
* get characters numeric value.
* e.g.: '0' to 0
*/
fun Char.toNumericValue(): Int = this - '0'
fun Char.caseToIndexedValue(): Int = this - 'a'
// fun Char.isLowerCase() = this in 'a'..'z'
//
// fun Char.isUpperCase() = this in 'A'..'Z'
/**
* make triple. e.g.:`1 to 2 to 3`
*/
infix fun <A, B, C> Pair<A, B>.to(c: C): Triple<A, B, C> = Triple(this.first, this.second, c)
fun YesNo(b: Boolean): String = if (b) Yes else No
val Yes = "Yes"
val No = "No"
fun YES_NO(b: Boolean): String = if (b) YES else NO
val YES = "YES"
val NO = "NO"
fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> Array<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> MutableList<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun IntArray.changeMinOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.min(this[i], v) }
fun IntArray.changeMaxOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.max(this[i], v) }
fun LongArray.changeMinOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.min(this[i], v) }
fun LongArray.changeMaxOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.max(this[i], v) }
fun IntArray.plusAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].plusMod(v) }
fun IntArray.minusAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].minusMod(v) }
fun IntArray.timesAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].timesMod(v) }
fun IntArray.divAssignMod(i: Int, v: Int): Unit = run { this[i] = this[i].divMod(v) }
fun IntArray.powAssignMod(i: Int, v: Long): Unit = run { this[i] = this[i].powMod(v) }
fun LongArray.plusAssignMod(i: Int, v: Int): Unit = run {
this[i] = (this[i] % mod).toInt().plusMod(v).toLong()
}
fun LongArray.minusAssignMod(i: Int, v: Int): Unit = run {
this[i] = (this[i] % mod).toInt().minusMod(v).toLong()
}
fun LongArray.timesAssignMod(i: Int, v: Int): Unit = run {
this[i] = (this[i] % mod).toInt().timesMod(v).toLong()
}
fun LongArray.divAssignMod(i: Int, v: Int): Unit = run {
this[i] = (this[i] % mod).toInt().divMod(v).toLong()
}
fun LongArray.powAssignMod(i: Int, v: Long): Unit = run {
this[i] = (this[i] % mod).toInt().powMod(v).toLong()
}
/**
* same usage as `IntArray.scan`, but it will faster than that.
*/
inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `LongArray.scan`, but it will faster than that.
*/
inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `IntArray.scanReduce`, but it will faster than that.
*/
inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
/**
* same usage as `LongArray.scanReduce`, but it will faster than that.
*/
inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
}
// endregion kokomade template dayo (^o^)