結果
問題 |
No.1750 ラムドスウイルスの感染拡大-hard
|
ユーザー |
|
提出日時 | 2022-01-26 23:06:21 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 609 ms / 2,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 15,958 ms |
コンパイル使用メモリ | 444,156 KB |
実行使用メモリ | 60,576 KB |
最終ジャッジ日時 | 2024-12-23 18:59:49 |
合計ジャッジ時間 | 32,648 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
const val MOD = 998244353 class Matrix(val row: Int, val column: Int, val state: Array<LongArray>) { constructor(row: Int, column: Int): this(row, column, Array(row){ LongArray(column) }) operator fun times(other: Matrix): Matrix { require(column == other.row) val result = Array(row){LongArray(other.column)} for (i in 0 until row) { for (j in 0 until other.column) { var sum = 0L for (k in 0 until column) { sum += state[i][k] * other.state[k][j] % MOD } result[i][j] = sum % MOD } } return Matrix(row, other.column, result) } fun pow(exp: Long): Matrix { require(row == column) var e = exp var result = E(row) var b = this while (e > 0) { if (e and 1 == 1L) { result *= b } e = e shr 1 b *= b } return result } companion object { fun E(size: Int): Matrix { return Matrix(size, size, Array(size){i -> LongArray(size){j -> if (i == j) 1 else 0} }) } } } fun main() { val (n, m, t) = readLine()!!.trim().split(' ').let{(n, m, t) -> Triple(n.toInt(), m.toInt(), t.toLong())} val roads = List(m){ val (u, v) = readLine()!!.trim().split(' ').map(String::toInt) u to v } val matrix = Matrix(n, n) for ((u, v) in roads) { matrix.state[u][v] += 1L matrix.state[v][u] += 1L } val initial = Matrix(n, 1).also { it.state[0][0] = 1L } val result = matrix.pow(t) * initial println(result.state[0][0]) }