結果

問題 No.314 ケンケンパ
ユーザー zeronosu77108zeronosu77108
提出日時 2021-02-10 22:54:07
言語 Kotlin
(1.9.23)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 260 ms
57,436 KB
testcase_01 AC 263 ms
57,432 KB
testcase_02 AC 271 ms
57,580 KB
testcase_03 AC 261 ms
57,668 KB
testcase_04 AC 262 ms
57,568 KB
testcase_05 AC 261 ms
57,656 KB
testcase_06 AC 263 ms
57,636 KB
testcase_07 AC 287 ms
57,500 KB
testcase_08 AC 264 ms
57,484 KB
testcase_09 AC 261 ms
57,492 KB
testcase_10 AC 260 ms
57,612 KB
testcase_11 AC 263 ms
57,764 KB
testcase_12 AC 262 ms
57,592 KB
testcase_13 AC 295 ms
57,632 KB
testcase_14 AC 266 ms
57,756 KB
testcase_15 AC 264 ms
57,656 KB
testcase_16 AC 262 ms
57,488 KB
testcase_17 AC 259 ms
57,684 KB
testcase_18 AC 261 ms
57,632 KB
testcase_19 AC 261 ms
57,624 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