結果

問題 No.314 ケンケンパ
コンテスト
ユーザー zeronosu77108
提出日時 2021-02-10 22:54:07
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 295 ms / 1,000 ms
コード長 993 bytes
コンパイル時間 11,901 ms
コンパイル使用メモリ 449,836 KB
実行使用メモリ 57,764 KB
最終ジャッジ日時 2024-07-08 10:14:45
合計ジャッジ時間 18,543 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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