結果

問題 No.1693 Invasion
ユーザー ポール
提出日時 2021-10-02 00:13:07
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 686 ms / 2,000 ms
コード長 3,109 bytes
コンパイル時間 15,576 ms
コンパイル使用メモリ 453,732 KB
実行使用メモリ 96,852 KB
最終ジャッジ日時 2024-07-19 17:52:34
合計ジャッジ時間 28,100 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:6:10: warning: variable 'n' is never used
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
         ^
Main.kt:94:13: warning: name shadowed: e
        var e = e
            ^

ソースコード

diff # 

import java.util.*

fun main() {
    val ONE = ModInt(1)

    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    var a = readLine()!!.splitToSequence(" ").map(String::toInt).toSortedSet()

    val frac = Array(m+1) {ONE}
    for (i in 2..frac.lastIndex) {
        frac[i] = frac[i-1] * i
    }
    val finv = Array(m+1) {ONE / frac[it]}

    val prs = IntArray(m+1)
    var newcomer: SortedSet<Int> = sortedSetOf(0)
    for (s in 1..m) {
        a = a.subSet(0, m-newcomer.first()+1)
        val tmp = newcomer
        newcomer = sortedSetOf()
        for (ai in a) {
            for (t in tmp) {
                val nxt = ai + t
                if (nxt < s) continue
                else if (nxt <= m) {
                    if (prs[nxt] == 0) {
                        newcomer.add(nxt)
                        prs[nxt] = s
                    }
                } else break
            }
        }
        if (newcomer.isEmpty()) break
    }

    var ans = if (prs[m] == 0) ONE else ModInt(2)
    for (c in 1 until m) {
        if (prs[c] == 0) continue
        ans += frac[m-prs[c]] * finv[c-prs[c]] * finv[m-c]
    }
    println(ans)

}

class ModInt {
    val v: Long

    constructor(v: Int) {
        this.v = when {
            v >= 0 -> v % MOD
            else -> (v % MOD) + MOD
        }
    }

    constructor(v: Long) {
        this.v = when {
            v >= 0 -> v % MOD
            else -> (v % MOD) + MOD
        }
    }

    override fun toString() = v.toString()
    fun toInt() = v.toInt()
    fun toLong() = v
    override fun equals(other: Any?): Boolean {
        return if (other is ModInt) v == other.v else false
    }

    override fun hashCode() = 31 * 17 + v.hashCode()

    operator fun unaryPlus() = this
    operator fun unaryMinus() = ModInt(-this.v)

    private operator fun plus(o: Long) = ModInt(this.v + o)
    operator fun plus(o: ModInt) = this.plus(o.v)
    operator fun plus(o: Int) = this.plus(o.toLong())
    private operator fun minus(o: Long) = ModInt(this.v - o)
    operator fun minus(o: ModInt) = this.minus(o.v)
    operator fun minus(o: Int) = this.minus(o.toLong())
    private operator fun times(o: Long) = ModInt(this.v * o)
    operator fun times(o: ModInt) = this.times(o.v)
    operator fun times(o: Int) = this.times(o.toLong())
    operator fun div(o: ModInt) = this.times(o.pow(MOD - 2))
    operator fun div(o: Int) = this.times(o.powMod(MOD - 2))

    operator fun inc() = this.plus(1)
    operator fun dec() = this.minus(1)

    fun pow(e: Long): ModInt {
        assert(e >= 0)
        if (this.v == 1L) return ModInt(1)
        var ans = ModInt(1)
        var b = this;
        var e = e
        while (e != 0L) {
            if (e % 2 == 1L) ans *= b
            b *= b
            e /= 2
        }
        return ans
    }

    fun pow(e: Int) = pow(e.toLong())

    companion object {
        const val MOD = 998244353L
    }
}

fun Long.powMod(e: Long) = ModInt(this).pow(e)
fun Long.powMod(e: Int) = ModInt(this).pow(e.toLong())
fun Int.powMod(e: Long) = ModInt(this).pow(e)
fun Int.powMod(e: Int) = ModInt(this).pow(e.toLong())
0