結果

問題 No.1693 Invasion
ユーザー ポールポール
提出日時 2021-10-02 00:13:07
言語 Kotlin
(1.9.10)
結果
AC  
実行時間 756 ms / 2,000 ms
コード長 3,109 bytes
コンパイル時間 17,973 ms
コンパイル使用メモリ 439,988 KB
実行使用メモリ 67,460 KB
最終ジャッジ日時 2023-09-27 00:11:35
合計ジャッジ時間 32,045 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 370 ms
57,092 KB
testcase_01 AC 366 ms
57,836 KB
testcase_02 AC 374 ms
59,264 KB
testcase_03 AC 372 ms
57,148 KB
testcase_04 AC 376 ms
57,308 KB
testcase_05 AC 394 ms
57,768 KB
testcase_06 AC 389 ms
57,396 KB
testcase_07 AC 380 ms
57,460 KB
testcase_08 AC 381 ms
57,384 KB
testcase_09 AC 677 ms
65,492 KB
testcase_10 AC 622 ms
65,116 KB
testcase_11 AC 550 ms
62,784 KB
testcase_12 AC 673 ms
67,460 KB
testcase_13 AC 556 ms
62,992 KB
testcase_14 AC 575 ms
63,060 KB
testcase_15 AC 604 ms
60,916 KB
testcase_16 AC 590 ms
62,900 KB
testcase_17 AC 364 ms
57,224 KB
testcase_18 AC 745 ms
67,424 KB
testcase_19 AC 509 ms
62,440 KB
testcase_20 AC 376 ms
57,248 KB
testcase_21 AC 736 ms
65,328 KB
testcase_22 AC 682 ms
65,116 KB
testcase_23 AC 756 ms
65,404 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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