結果

問題 No.314 ケンケンパ
ユーザー 👑 zeronosu77108zeronosu77108
提出日時 2021-02-10 22:54:07
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 291 ms / 1,000 ms
コード長 993 bytes
コンパイル時間 17,574 ms
コンパイル使用メモリ 423,688 KB
実行使用メモリ 55,848 KB
最終ジャッジ日時 2023-09-22 19:05:38
合計ジャッジ時間 24,973 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 286 ms
53,988 KB
testcase_01 AC 287 ms
53,768 KB
testcase_02 AC 285 ms
53,936 KB
testcase_03 AC 283 ms
53,800 KB
testcase_04 AC 291 ms
53,792 KB
testcase_05 AC 281 ms
53,560 KB
testcase_06 AC 288 ms
53,564 KB
testcase_07 AC 288 ms
53,916 KB
testcase_08 AC 284 ms
53,764 KB
testcase_09 AC 285 ms
53,760 KB
testcase_10 AC 283 ms
53,736 KB
testcase_11 AC 288 ms
53,840 KB
testcase_12 AC 288 ms
53,704 KB
testcase_13 AC 288 ms
53,632 KB
testcase_14 AC 288 ms
55,848 KB
testcase_15 AC 282 ms
53,724 KB
testcase_16 AC 281 ms
53,812 KB
testcase_17 AC 281 ms
53,696 KB
testcase_18 AC 285 ms
53,676 KB
testcase_19 AC 283 ms
53,844 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fun main() {
    val n = readLine()!!.toInt()

    val a = arrayOf( arrayOf(0L,1,1), arrayOf(1L,0,0), arrayOf(0L,1,0))
    val an = pow(a, n)

    val ans = mul(an, arrayOf( arrayOf(1L), arrayOf(0L), arrayOf(0L))).sumOf { it.first() }
    println((ans + 1_000_000_007) % 1_000_000_007)
}

fun pow(A : Array<Array<Long>>, n : Int): Array<Array<Long>> {
    var t = n
    var res = arrayOf( arrayOf(1L,0,0), arrayOf(0L,1,0), arrayOf(0L,0,1))
    var a = A
    while (t > 0) {
        if (t and 1 == 1) res = mul(res, a)
        a = mul(a, a)
        t /= 2
    }

    return res
}

fun mul(A : Array<Array<Long>>, B : Array<Array<Long>>): Array<Array<Long>> {
    val res = Array(A.size) { Array(B.first().size) { 0L } }
    for (i in 0 until A.size) {
        for (j in 0 until B.first().size) {
            for (k in 0 until B.size) {
                res[i][j] += (A[i][k] * B[k][j]) % 1_000_000_007
                res[i][j] %= 1_000_000_007L
            }
        }
    }
    return res
}
0