結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー | yudedako |
提出日時 | 2022-01-26 23:06:21 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 544 ms / 2,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 17,698 ms |
コンパイル使用メモリ | 423,444 KB |
実行使用メモリ | 56,984 KB |
最終ジャッジ日時 | 2023-08-25 11:58:14 |
合計ジャッジ時間 | 33,415 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 295 ms
53,264 KB |
testcase_01 | AC | 295 ms
53,200 KB |
testcase_02 | AC | 295 ms
53,064 KB |
testcase_03 | AC | 298 ms
53,100 KB |
testcase_04 | AC | 397 ms
53,984 KB |
testcase_05 | AC | 299 ms
53,040 KB |
testcase_06 | AC | 300 ms
53,076 KB |
testcase_07 | AC | 298 ms
53,188 KB |
testcase_08 | AC | 376 ms
55,904 KB |
testcase_09 | AC | 376 ms
56,008 KB |
testcase_10 | AC | 375 ms
55,764 KB |
testcase_11 | AC | 398 ms
56,084 KB |
testcase_12 | AC | 413 ms
56,676 KB |
testcase_13 | AC | 408 ms
56,868 KB |
testcase_14 | AC | 539 ms
56,764 KB |
testcase_15 | AC | 541 ms
56,728 KB |
testcase_16 | AC | 544 ms
56,640 KB |
testcase_17 | AC | 517 ms
56,704 KB |
testcase_18 | AC | 524 ms
56,496 KB |
testcase_19 | AC | 515 ms
56,568 KB |
testcase_20 | AC | 466 ms
56,984 KB |
testcase_21 | AC | 500 ms
56,688 KB |
testcase_22 | AC | 396 ms
56,632 KB |
testcase_23 | AC | 525 ms
56,848 KB |
testcase_24 | AC | 382 ms
56,404 KB |
testcase_25 | AC | 390 ms
56,400 KB |
testcase_26 | AC | 359 ms
55,976 KB |
testcase_27 | AC | 332 ms
54,076 KB |
testcase_28 | AC | 347 ms
53,896 KB |
testcase_29 | AC | 306 ms
53,104 KB |
testcase_30 | AC | 422 ms
56,776 KB |
testcase_31 | AC | 417 ms
56,984 KB |
testcase_32 | AC | 417 ms
56,676 KB |
testcase_33 | AC | 415 ms
56,796 KB |
ソースコード
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]) }