結果
問題 | No.1112 冥界の音楽 |
ユーザー |
![]() |
提出日時 | 2020-07-10 22:26:15 |
言語 | Swift (5.10.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,899 bytes |
コンパイル時間 | 1,456 ms |
コンパイル使用メモリ | 130,064 KB |
実行使用メモリ | 36,608 KB |
最終ジャッジ日時 | 2024-05-07 22:22:24 |
合計ジャッジ時間 | 18,663 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
15,744 KB |
testcase_01 | AC | 10 ms
9,580 KB |
testcase_02 | AC | 291 ms
10,752 KB |
testcase_03 | AC | 10 ms
9,704 KB |
testcase_04 | AC | 195 ms
10,496 KB |
testcase_05 | AC | 148 ms
10,240 KB |
testcase_06 | AC | 149 ms
10,368 KB |
testcase_07 | AC | 9 ms
9,576 KB |
testcase_08 | AC | 10 ms
9,576 KB |
testcase_09 | AC | 58 ms
9,728 KB |
testcase_10 | AC | 149 ms
9,984 KB |
testcase_11 | AC | 197 ms
10,496 KB |
testcase_12 | AC | 196 ms
10,240 KB |
testcase_13 | AC | 9 ms
9,600 KB |
testcase_14 | AC | 1,472 ms
15,232 KB |
testcase_15 | AC | 944 ms
14,080 KB |
testcase_16 | AC | 1,088 ms
15,488 KB |
testcase_17 | AC | 1,257 ms
14,976 KB |
testcase_18 | AC | 1,256 ms
15,232 KB |
testcase_19 | AC | 950 ms
14,208 KB |
testcase_20 | AC | 1,137 ms
15,360 KB |
testcase_21 | AC | 1,353 ms
15,488 KB |
testcase_22 | AC | 1,407 ms
14,720 KB |
testcase_23 | AC | 855 ms
13,568 KB |
testcase_24 | TLE | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
ソースコード
struct Scanner { private var stack = [String]() private var index = 0 mutating func peek() -> String { if stack.count == index { stack += readLine()!.split(separator: " ").map{ String($0) } } return stack[index] } mutating func next() -> String { let value = peek() index += 1 return value } mutating func nextInt() -> Int { return Int(next())! } mutating func nextDouble() -> Double { return Double(next())! } } let MOD = 1000000007 struct Zn { let n: Int init(_ n: Int) { self.n = n } static func + (lhs: Self, rhs: Self) -> Self { let n = lhs.n + rhs.n return Zn(n < MOD ? n : n - MOD) } static func - (lhs: Self, rhs: Self) -> Self { Zn((lhs.n - rhs.n + MOD) % MOD) } static func * (lhs: Self, rhs: Self) -> Self { Zn((lhs.n * rhs.n) % MOD) } static func += (lhs: inout Self, rhs: Self) { lhs = lhs + rhs } } let U = 6 * 6 * 6 struct Matrix { var A = [Zn](repeating: Zn(0), count: U * U) subscript(k: (Int, Int)) -> Zn { get { return A[k.0 * U + k.1] } set { A[k.0 * U + k.1] = newValue } } static var E: Self { var value = Matrix() for i in 0 ..< U { value[(i, i)] = Zn(1) } return value } static func * (lhs: Self, rhs: Self) -> Self { var value = Matrix() for i in 0 ..< U { for j in 0 ..< U { for k in 0 ..< U { value[(i, j)] += lhs[(i, k)] * rhs[(k, j)] } } } return value } func pow(_ k: Int) -> Self { if k == 0 { return .E } else if k % 2 == 1 { return self.pow(k - 1) * self } else { return (self * self).pow(k / 2) } } } var scanner = Scanner() let K = scanner.nextInt() let M = scanner.nextInt() let N = scanner.nextInt() var matrix = Matrix() func index(_ i: Int, _ j: Int, _ k: Int) -> Int { (i * 6 + j) * 6 + k } var table = [Bool](repeating: false, count: 6 * 6 * 6) for _ in 0 ..< M { let P = scanner.nextInt() - 1 let Q = scanner.nextInt() - 1 let R = scanner.nextInt() - 1 table[index(P, Q, R)] = true } for i in 0 ..< K { for j in 0 ..< K { for k in 0 ..< K { for l in 0 ..< K { if table[index(j, k, l)] { matrix[(index(j, k, l), index(i, j, k))] += Zn(1) } } } } } matrix = matrix.pow(N - 3) var answer = Zn(0) for i in 0 ..< U where i % 6 == 0 { for j in 0 ..< U where table[j] && j / 36 == 0 { answer += matrix[(i, j)] } } print(answer.n)