結果
問題 | 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 ^
ソースコード
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 = newcomernewcomer = sortedSetOf()for (ai in a) {for (t in tmp) {val nxt = ai + tif (nxt < s) continueelse 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) continueans += frac[m-prs[c]] * finv[c-prs[c]] * finv[m-c]}println(ans)}class ModInt {val v: Longconstructor(v: Int) {this.v = when {v >= 0 -> v % MODelse -> (v % MOD) + MOD}}constructor(v: Long) {this.v = when {v >= 0 -> v % MODelse -> (v % MOD) + MOD}}override fun toString() = v.toString()fun toInt() = v.toInt()fun toLong() = voverride 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() = thisoperator 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 = ewhile (e != 0L) {if (e % 2 == 1L) ans *= bb *= be /= 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())