結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー cedretaber
提出日時 2020-03-27 02:33:42
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,271 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 105,272 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 05:48:25
合計ジャッジ時間 1,348 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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