結果
問題 | No.1336 Union on Blackboard |
ユーザー |
|
提出日時 | 2021-01-15 21:27:22 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 437 ms / 2,000 ms |
コード長 | 3,344 bytes |
コンパイル時間 | 16,248 ms |
コンパイル使用メモリ | 459,588 KB |
実行使用メモリ | 109,904 KB |
最終ジャッジ日時 | 2024-11-26 13:18:48 |
合計ジャッジ時間 | 28,765 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
import java.io.PrintWriterimport java.util.*import kotlin.math.*// region ModIntclass ModInt(x: Long) {companion object {const val MOD = 1000000007L//const val MOD = 998244353L}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"}}fun Long.toModInt(): ModInt {return ModInt(this)}fun Int.toModInt(): ModInt {return ModInt(this)}const val fac_size = 600000var fac_initialized = falseval arr_fac = Array(fac_size) { ModInt(1) }val arr_invfac = Array(fac_size) { ModInt(1) }fun facInitialize() {for (i in 1 until fac_size) {arr_fac[i] = arr_fac[i - 1] * ModInt(i)}arr_invfac[fac_size - 1] = arr_fac[fac_size - 1].inv()for (i in fac_size - 2 downTo 1) {arr_invfac[i] = arr_invfac[i + 1] * ModInt(i + 1)}fac_initialized = true}fun fac(n: Int): ModInt {if (!fac_initialized) facInitialize()return arr_fac[n]}fun fac(n: Long): ModInt {return fac(n.toInt())}fun invfac(n: Int): ModInt {if (!fac_initialized) facInitialize()return arr_invfac[n]}fun invfac(n: Long): ModInt {return invfac(n.toInt())}fun comb(n: Long, k: Long): ModInt {return if (k in 0..n) {if (!fac_initialized) facInitialize()arr_fac[n.toInt()] * arr_invfac[k.toInt()] * arr_invfac[(n - k).toInt()]} else {ModInt(0)}}fun comb2(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}// endregionfun PrintWriter.solve() {val numCases = nextInt()case@ for (_i in 0 until numCases) {val n = nextInt()val a = Array(n) { nextInt().toModInt() }println(a.map { it + ModInt(1) }.fold(ModInt(1), { x, y -> x * y }) - ModInt(1))}}fun main() {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}// 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