結果

問題 No.8036 Restricted Lucas (Easy)
コンテスト
ユーザー nebukuro09
提出日時 2018-04-02 00:15:47
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,321 bytes
コンパイル時間 1,602 ms
コンパイル使用メモリ 149,212 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 00:09:13
合計ジャッジ時間 1,811 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long zero = false;
immutable long one = true;
immutable long two = one << one;
immutable long three = two + one;
immutable long four = two << one;
immutable long five = four + one;
immutable long six = four + two;
immutable long seven = four + three;
immutable long eight = four << one;
immutable long nine = eight + one;
immutable long ten = eight + two;

immutable string str_A = ((one << six) + one).to!char.to!string;
immutable string str_B = ((one << six) + two).to!char.to!string;
immutable string op_mul = (ten + ten + ten + ten + two).to!char.to!string;
immutable string op_mod = (ten + ten + ten + seven).to!char.to!string;

immutable long MOD = ten ^^ nine + seven;

long mul(long A, long B) {
    A = mod(A, MOD);
    B = mod(B, MOD);
    return mixin(str_A ~ op_mul ~ str_B);
}

long mod(long A, long B) {
    return mixin(str_A ~ op_mod ~ str_B);
}

long[][] matmul(int N, long[][] m_one, long[][] m_two) {
    auto ret = new long[][](N, N);
    foreach (i; zero..N) {
        foreach (j; zero..N) {
            ret[i][j] = zero;
            foreach (k; zero..N) {
                ret[i][j] += mul(m_one[i][k], m_two[k][j]);
                ret[i][j] = mod(ret[i][j], MOD);
            }
        }
    }
    return ret;
}

long[][] matpow(int N, long K, long[][] mat) {
    auto ret = new long[][](N, N);
    foreach (i; zero..N)
        foreach (j; zero..N)
            ret[i][j] = i == j ? one : zero;

    while (K > zero) {
        if ((K & one) == one)
            ret = matmul(N, ret, mat);
        mat = matmul(N, mat, mat);
        K >>= one;
    }

    return ret;
}

long fib(long n) {
    long[][] m = [[one, one], [one, zero]];
    return matpow(two, n, m)[zero][zero];
}

void main() {
    int T = readln.chomp.to!int;
    while (T--) {
        long N = readln.chomp.to!long;
        if (N == one) {
            one.writeln;
        } else if (N == two) {
            three.writeln;
        } else {
            long a = fib(N + one);
            long b = fib(N - three);
            long c = mod(a - b, MOD);
            long d = mod(c + MOD, MOD);
            d.writeln;
        }
    }
}
0