結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-10-17 22:35:24 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 1,152 ms / 2,000 ms |
コード長 | 4,419 bytes |
コンパイル時間 | 17,921 ms |
コンパイル使用メモリ | 458,584 KB |
実行使用メモリ | 88,220 KB |
最終ジャッジ日時 | 2024-09-17 19:47:13 |
合計ジャッジ時間 | 57,119 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
import java.io.PrintWriterimport java.util.*fun PrintWriter.solve() {val numCases = nextInt()case@ for (_i in 0 until numCases) {val n = nextLong()val b = arrayOf(arrayOf(1, 0, 0, 0, 1, 1),arrayOf(0, 1, 0, 1, 0, 1),arrayOf(0, 0, 1, 1, 1, 0),arrayOf(3, 0, 0, 0, 0, 0),arrayOf(0, 3, 0, 0, 0, 0),arrayOf(0, 0, 3, 0, 0, 0))val mat = Matrix(b).pow(n).matval p = mat[3][0] + ModInt(3) * mat[3][3]println(p / ModInt(3).pow(n + 1))}}// region Matrixclass Matrix(val mat: Array<Array<ModInt>>) {private val n = mat.sizeconstructor(a: Array<Array<Int>>) : this(Array(a.size) { i -> Array(a.size) { j -> a[i][j].toModInt() } })constructor(a: Array<Array<Long>>) : this(Array(a.size) { i -> Array(a.size) { j -> a[i][j].toModInt() } })operator fun plus(other: Matrix): Matrix {val b = mat.copyOf()for (i in 0 until n) {for (j in 0 until n) {b[i][j] += other.mat[i][j]}}return Matrix(b)}operator fun minus(other: Matrix): Matrix {val b = mat.copyOf()for (i in 0 until n) {for (j in 0 until n) {b[i][j] -= other.mat[i][j]}}return Matrix(b)}operator fun times(other: Matrix): Matrix {val b = zero(n).matfor (k in 0 until n) {for (i in 0 until n) {for (j in 0 until n) {b[i][j] += mat[i][k] * other.mat[k][j]}}}return Matrix(b)}fun pow(exp: Long): Matrix {if (exp == 0L) return e(n)var a = pow(exp shr 1)a *= aif (exp and 1L == 0L) return areturn this * a}override fun toString(): String {return mat.joinToString("\n") { "[${it.joinToString()}]" }}}fun zero(n: Int): Matrix {return Matrix(Array(n) { Array(n) { ModInt(0) } })}fun e(n: Int): Matrix {return Matrix(Array(n) { i -> Array(n) { j -> ModInt(if (i == j) 1 else 0) } })}// endregion// 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)}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}// endregionfun main() {Thread(null, {val writer = PrintWriter(System.out, !false)writer.solve()writer.flush()}, "solve", 1.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