Блог пользователя Petr

Автор Petr, история, 6 месяцев назад, По-английски
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Thanks for the mention!

Regarding the comments about the ModInt class: I experimented with it and found it is slightly slower (even with inline class) than the global infix functions, and I find it annoying to convert between ModInt, Int and Long. I also like the fact that by using a global "mp" I am more explicit about which operations are modded or not.

The decision to stick to "mp" was made a long time ago (since I am orange ish). I know many others have used ModInt class and found success, so I would not be surprised if I end up switching to using ModInt later.

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Thanks for sharing! According to this comment and other sources in the internet, it's impossible in Kotlin for code like "val == 0" to work when val is ModInt, so ModInt will come with its own caveats...

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    @JvmInline
    @Suppress("NOTHING_TO_INLINE")
    private value class ModInt(val x: Int) {
        inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
        inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
        inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
        fun power(p_: Int): ModInt {
            var a = this
            var res = ModInt(1)
            var p = p_
            while (p != 0) {
                if ((p and 1) == 1) res *= a
                a *= a
                p = p shr 1
            }
            return res
        }
    
        inline operator fun div(other: ModInt) = this * other.inv()
        inline fun inv() = power(MOD - 2)
    
        companion object {
            inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
            inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
        }
    }
    
    @JvmInline
    private value class ModIntArray(private val storage:IntArray) {
        operator fun get(index: Int) = ModInt(storage[index])
        operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
        val size get() = storage.size
    }
    private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })
    

    Didn't have performance problems with it. But, can agree, it's not very handy to cast/work with constants.