結果

問題 No.1693 Invasion
コンテスト
ユーザー ポール
提出日時 2021-10-01 23:41:32
言語 Kotlin
(2.1.0)
結果
TLE  
実行時間 -
コード長 3,242 bytes
コンパイル時間 16,876 ms
コンパイル使用メモリ 462,256 KB
実行使用メモリ 130,900 KB
最終ジャッジ日時 2024-07-19 16:50:57
合計ジャッジ時間 26,043 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:6:10: warning: variable 'n' is never used
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
         ^
Main.kt:8:9: warning: variable 'amin' is never used
    val amin = a.first()
        ^
Main.kt:101: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 amin = a.first()

    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]}

    var canAll = false
    var ans = ONE
    var ts: SortedSet<Int> = sortedSetOf(0)
    var newcomer: SortedSet<Int> = sortedSetOf(0)
    for (s in 1 until m) {
        a = a.subSet(0, m-ts.first()+1)
        ts = ts.subSet(s, m).toSortedSet()
        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) {
                    newcomer.add(nxt)
                    ts.add(nxt)
                }
                else {
                    if (nxt == m) canAll = true
                    break
                }
            }
        }
        if (ts.isEmpty()) break

        var sum = ModInt(0)
        for (t in ts) {
            sum += finv[t-s] * finv[m-t-1]
        }
        ans += sum * frac[m-s-1]
    }
    if (canAll) ans++
    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