結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー cedretaber
提出日時 2020-03-27 02:33:42
言語 D
(dmd 2.091.0)
結果
AC  
実行時間 2 ms
コード長 2,271 Byte
コンパイル時間 716 ms
使用メモリ 8,944 KB
最終ジャッジ日時 2020-03-27 02:33:45

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 1 ms
8,944 KB
sample2.txt AC 1 ms
8,944 KB
sample3.txt AC 1 ms
8,900 KB
test01.txt AC 1 ms
8,940 KB
test02.txt AC 1 ms
6,900 KB
test03.txt AC 2 ms
8,944 KB
test04.txt AC 2 ms
8,944 KB
test05.txt AC 1 ms
8,940 KB
test06.txt AC 2 ms
8,900 KB
test07.txt AC 2 ms
6,900 KB
test08.txt AC 1 ms
8,940 KB
test09.txt AC 2 ms
8,896 KB
test10.txt AC 1 ms
6,900 KB
test11.txt AC 1 ms
8,944 KB
test12.txt AC 1 ms
6,900 KB
テストケース一括ダウンロード

ソースコード

diff #
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

struct Matrix(N, size_t height, size_t width)
{
    N M;
    N[width][height] arr;

    this(N[width][height] arr, N M = 0) {
        this.arr = arr;
        this.M = M;
    }

    pure nothrow @nogc
    Matrix!(N, height, rhs_width) opBinary(string op, size_t rhs_width)(Matrix!(N, width, rhs_width) rhs) {
        static if (op == "*") {
            N[rhs_width][height] res;
            foreach (y; 0..height) {
                foreach (x; 0..rhs_width) {
                    foreach (i; 0..width) {
                        auto s = this.arr[y][i] * rhs.arr[i][x];
                        if (this.M) s %= this.M;
                        res[y][x] += s;
                        if (this.M) res[y][x] %= this.M;
                    }
                }
            }
            return Matrix!(N, height, rhs_width)(res, this.M);
        } else static if (op == "+") {
            N[rhs_width] res;
            foreach (y; 0..height) {
                foreach (x; 0..rhs_width) {
                    res[y][x] = this.arr[y][x] + rhs.arr[y][x];
                    if (this.M) res[y][x] %= this.M;
                }
            }
            return Matrix!(N, height, rhs_width)(res, this.M);
        } else {
            static assert(0, "Operator "~op~" not implemented");
        }
    }

    pure nothrow @nogc
    Matrix!(N, height, width) opBinary(string op)(N n) {
        static if (op == "^^" && height == width) {
            N[width][height] rr;
            foreach (i; 0..width) rr[i][i] = 1;
            auto r = Matrix!(N, height, width)(rr, M);
            auto x = this;
            while (n) {
                if (n%2 == 1) r = r * x;
                x = x * x;
                n /= 2;
            }
            return r;
        } else {
            static assert(0, "Operator "~op~" not implemented");
        }
    }
}

Matrix!(N, h, w) matrix(N, size_t h, size_t w)(N[w][h] arr, N M = 0)
{
    return Matrix!(N, h, w)(arr, M);
}

void main()
{
    auto nm = readln.split.to!(long[]);
    auto N = nm[0];
    auto M = nm[1];

    auto x = matrix!(long, 1, 2)([[0, 1]]) * matrix!(long, 2, 2)([[0, 1], [1, 1]], M)^^(N-2);
    writeln(x.arr[0][1]);
}
0