結果

問題 No.8037 Restricted Lucas (Hard)
ユーザー satanic
提出日時 2018-04-02 02:01:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,837 bytes
コンパイル時間 1,367 ms
コンパイル使用メモリ 89,212 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:27:23
合計ジャッジ時間 1,831 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <vector>
#include <functional>
#define int long long
int z;
int o = !z;
int two = o << o;
int seven = std::minus<int>()(two << two, o);
int MOD;
std::vector<std::vector<int>> a, b;
int suc(int& x) {
    return x = std::plus<int>()(x, o);
}
std::vector<std::vector<int>> mul(std::vector<std::vector<int>> x, std::vector<std::vector<int>> y) {
    std::vector<std::vector<int>> r(x.size(), std::vector<int>(y[z].size(), z));
    for (int i = z; i < x.size(); suc(i)) {
        for (int j = z; j < y[z].size(); suc(j)) {
            for (int k = z; k < x[z].size(); suc(k)) {
                r[i][j] = std::modulus<int>()(std::plus<int>()(r[i][j], std::multiplies<int>()(x[i][k], y[k][j])), MOD);
            }
        }
    }
    return r;
}
void pow_(int p) {
    while (p) {
        if (p & o) a = mul(a, b);
        b = mul(b, b);
        p >>= o;
    }
}
int solve(int n) {
    if (n == o) return o;
    a = std::vector<std::vector<int>>(two, std::vector<int>(two, o));
    a[o][o] = z;
    b = a;
    pow_(std::minus<int>()(n, two));
    return std::modulus<int>()(std::plus<int>()(a[z][z], (a[z][o] << o)), MOD);
}
void init_mod() {
    std::string s;
    s = std::plus<std::string>()(s, std::to_string(o));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(z));
    s = std::plus<std::string>()(s, std::to_string(seven));
    MOD = std::stoi(s);
}
signed main() {
    init_mod();
    int t;
    std::cin >> t;
    for (int _ = z; _ < t; suc(_)) {
        int n;
        std::cin >> n;
        std::cout << solve(n) << std::endl;
    }
    return z;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0