結果

問題 No.1693 Invasion
ユーザー ポールポール
提出日時 2021-10-02 00:07:15
言語 Kotlin
(1.9.23)
結果
WA  
実行時間 -
コード長 3,114 bytes
コンパイル時間 18,809 ms
コンパイル使用メモリ 431,532 KB
実行使用メモリ 67,628 KB
最終ジャッジ日時 2023-09-26 23:52:59
合計ジャッジ時間 34,003 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 368 ms
57,268 KB
testcase_01 AC 365 ms
57,160 KB
testcase_02 AC 370 ms
57,132 KB
testcase_03 AC 368 ms
57,580 KB
testcase_04 AC 364 ms
57,556 KB
testcase_05 AC 386 ms
57,372 KB
testcase_06 AC 387 ms
57,296 KB
testcase_07 AC 380 ms
57,484 KB
testcase_08 AC 386 ms
57,208 KB
testcase_09 AC 677 ms
65,652 KB
testcase_10 AC 615 ms
64,880 KB
testcase_11 AC 551 ms
62,536 KB
testcase_12 AC 660 ms
67,628 KB
testcase_13 AC 543 ms
63,016 KB
testcase_14 AC 572 ms
63,120 KB
testcase_15 AC 610 ms
61,344 KB
testcase_16 AC 578 ms
62,768 KB
testcase_17 WA -
testcase_18 AC 713 ms
67,448 KB
testcase_19 AC 491 ms
62,368 KB
testcase_20 AC 378 ms
57,500 KB
testcase_21 AC 729 ms
65,296 KB
testcase_22 AC 680 ms
64,780 KB
testcase_23 AC 742 ms
65,348 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 until 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