結果

問題 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())
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0