#226366 (Ruby) No.658 テトラナッチ数列 Hard

• 問題: No.658 テトラナッチ数列 Hard
• ユーザー: ciel
• 提出日時: 2017-12-27 20:22:19
• 言語: Ruby (3.4.1)
• 結果: TLE
• 実行時間: -
• コード長: 405 bytes
• コンパイル時間: 41 ms
• コンパイル使用メモリ: 7,424 KB
• 実行使用メモリ: 26,184 KB
• 最終ジャッジ日時: 2024-12-21 07:58:20
• 合計ジャッジ時間: 22,343 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	89 ms; 19,108 KB
testcase_01	AC	85 ms; 24,960 KB
testcase_02	AC	95 ms; 19,236 KB
testcase_03	AC	159 ms; 25,088 KB
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-

コンパイルメッセージ

Syntax OK

ソースコード

M=17
def mul(a,b)
	r=a.size.times.map{[0]*b[0].size}
	a.size.times{|y|
		b[0].size.times{|x|
			r[y][x]=b.size.times.reduce(0){|s,i|(s+a[y][i]*b[i][x])%M}
		}
	}
	r
end
A=[[1,1,1,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]]
E=[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
gets.to_i.times{
    n=gets.to_i
    a=A
    e=E
    while n>0
        e=mul(a,e) if n%2>0
        a=mul(a,a)
        n/=2
    end
    p e[-1][-1]
}