結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
![]() |
提出日時 | 2018-03-02 23:09:58 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 1,086 ms / 2,000 ms |
コード長 | 2,177 bytes |
コンパイル時間 | 858 ms |
コンパイル使用メモリ | 105,668 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-13 00:00:28 |
合計ジャッジ時間 | 6,516 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
import std.algorithm;import std.array;import std.conv;import std.math;import std.range;import std.stdio;import std.string;import std.typecons;T read(T)() { return readln.chomp.to!T; }T[] reads(T)() { return readln.split.to!(T[]); }alias readint = read!int;alias readints = reads!int;int calc(long n) {assert(n > 0);if (n <= 3) return 0;if (n == 4) return 1;auto m = new Mat4x4([[1, 1, 1, 1],[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 1, 0]]);const mod = 17;auto ret = m.pow(n - 1, mod);return ret.get(3, 0);}void main() {int q = readint;for (int i = 0; i < q; i++) {long n = read!long;int ans = calc(n);writeln(ans);}}class Mat4x4 {private const N = 4;private const int[][] _mat;this(const int[][] init) {assert(init.length == N);assert(init[0].length == init[1].length && init[0].length == N);_mat = init.dup;}int get(int r, int c) const {return _mat[r][c];}Mat4x4 mul(const Mat4x4 m, int mod) const {auto t = new int[][](N, N);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {int x = 0;for (int k = 0; k < N; k++) {x = (x + (_mat[i][k] * m.get(k, j)) % mod) % mod;}t[i][j] = x;}}return new Mat4x4(t);}Mat4x4 copy() const {return new Mat4x4(_mat);}Mat4x4 pow(long k, int mod) const {assert(k > 0);if (k == 1) return this.copy();auto m = this.pow(k / 2, mod);return k % 2 == 0? m.mul(m, mod): this.mul(m.mul(m, mod), mod);}void dump() const {writeln(_mat[0][0], " ", _mat[0][1], " ", _mat[0][2], " ", _mat[0][3]);writeln(_mat[1][0], " ", _mat[1][1], " ", _mat[1][2], " ", _mat[1][3]);writeln(_mat[2][0], " ", _mat[2][1], " ", _mat[2][2], " ", _mat[2][3]);writeln(_mat[3][0], " ", _mat[3][1], " ", _mat[3][2], " ", _mat[3][3]);}}