結果
問題 | No.2792 Security Cameras on Young Diagram |
ユーザー |
|
提出日時 | 2024-02-11 23:52:40 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 722 ms / 2,000 ms |
コード長 | 4,150 bytes |
コンパイル時間 | 18,998 ms |
コンパイル使用メモリ | 458,776 KB |
実行使用メモリ | 139,000 KB |
最終ジャッジ日時 | 2024-06-24 18:44:35 |
合計ジャッジ時間 | 34,971 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
import java.io.PrintWriterimport java.util.*import kotlin.math.*fun PrintWriter.solve() {val n = nextInt()val a = Array(n) { nextInt() } + arrayOf(0)var ans = ModInt(0)val cc = CombinationCalculator()var j = a[0]for (i in 0 until n) {while (j > a[i + 1]) {val v = cc.binom(i + j - 1L, j - 1L)if (j == a[i]) ans += vans += vj--}val v = cc.binom(i + j - 1L, j - 1L)if (j == a[i]) ans += v}println(ans)}// region ModIntclass ModInt(x: Long) {companion object {const val MOD = 998244353L//const val MOD = 1000000007L}constructor(y: Int) : this(y.toLong())val x = (x % MOD + MOD) % MODoperator fun plus(other: ModInt): ModInt {return ModInt(x + other.x)}operator fun minus(other: ModInt): ModInt {return ModInt(x - other.x)}operator fun times(other: ModInt): ModInt {return ModInt(x * other.x)}operator fun div(other: ModInt): ModInt {return this * other.inv()}fun pow(exp: Long): ModInt {if (exp == 0L) return ModInt(1L)var a = pow(exp shr 1)a *= aif (exp and 1L == 0L) return areturn this * a}fun inv(): ModInt {return this.pow(MOD - 2)}override fun equals(other: Any?): Boolean {if (this === other) return trueif (javaClass != other?.javaClass) return falseother as ModIntif (x != other.x) return falsereturn true}override fun hashCode(): Int {return x.hashCode()}override fun toString(): String {return "$x"}}class ModIntArray(n: Int) {private val a = LongArray(n) { 0L }constructor(n: Int, init: (Int) -> ModInt) : this(n) {for (i in 0 until n) {a[i] = init(i).x}}operator fun set(i: Int, x: ModInt) {a[i] = x.x}operator fun get(i: Int): ModInt {return ModInt(a[i])}fun joinToString(s: String = ", "): String {return a.joinToString(s)}}fun Long.toModInt() = ModInt(this)fun Int.toModInt() = ModInt(this)fun binomSimple(n: Long, k: Long): ModInt {var numer = ModInt(1)var denom = ModInt(1)for (i in 0 until k) {numer *= ModInt(n - i)denom *= ModInt(k - i)}return numer / denom}// endregionclass CombinationCalculator {companion object {private const val fac_size = 600000}private val arrFac = Array(fac_size) { ModInt(1) }private val arrInvfac = Array(fac_size) { ModInt(1) }init {for (i in 1 until fac_size) {arrFac[i] = arrFac[i - 1] * ModInt(i)}arrInvfac[fac_size - 1] = arrFac[fac_size - 1].inv()for (i in fac_size - 2 downTo 1) {arrInvfac[i] = arrInvfac[i + 1] * ModInt(i + 1)}}fun fac(n: Int): ModInt {return arrFac[n]}fun fac(n: Long): ModInt {return fac(n.toInt())}fun invfac(n: Int): ModInt {return arrInvfac[n]}fun invfac(n: Long): ModInt {return invfac(n.toInt())}fun binom(n: Long, k: Long): ModInt {return if (k in 0..n) {arrFac[n.toInt()] * arrInvfac[k.toInt()] * arrInvfac[(n - k).toInt()]} else {ModInt(0)}}}fun main() {Thread(null, {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}, "solve", abs(1L.shl(26))).apply { setUncaughtExceptionHandler { _, e -> e.printStackTrace(); kotlin.system.exitProcess(1) } }.apply { start() }.join()}// region Scannerprivate var st = StringTokenizer("")private val br = System.`in`.bufferedReader()fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()fun nextDouble() = next().toDouble()// endregion