結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー rsk0315rsk0315
提出日時 2019-08-09 06:03:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,652 bytes
コンパイル時間 1,021 ms
コンパイル使用メモリ 86,784 KB
最終ジャッジ日時 2024-11-14 21:32:02
合計ジャッジ時間 1,412 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:23:13: error: non-local lambda expression cannot have a capture-default
   23 | auto mod = [=](auto x) { return std::modulus<intmax_t>()(x, p); };
      |             ^

ソースコード

diff # 

#include <cstdio>
#include <cstdint>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <tuple>
#include <functional>

constexpr intmax_t zero = false;
constexpr intmax_t one = true;

auto add = std::plus<intmax_t>();
auto sub = std::minus<intmax_t>();
auto mul = std::multiplies<intmax_t>();

auto v = [](auto x) { return add(x, one); };
auto w = [](auto x) { return add(x, x); };

intmax_t two = w(one);
intmax_t p = v(w(v(w(v(w(w(w(w(w(w(w(v(w(w(v(w(w(w(v(w(v(w(w(v(w(w(v(w(v(w(w(w(v(w(v(w(v(w(w(v(w(v(w(one))))))))))))))))))))))))))))))))))))))))))));

auto mod = [=](auto x) { return std::modulus<intmax_t>()(x, p); };

using matrix = std::tuple<intmax_t, intmax_t, intmax_t, intmax_t>;

matrix matmul(matrix const& s, matrix const& t) {
  intmax_t a, b, c, d;
  intmax_t e, f, g, h;
  std::tie(a, b, c, d) = s;
  std::tie(e, f, g, h) = t;

  intmax_t i = mod(add(mul(a, e), mul(b, g)));
  intmax_t j = mod(add(mul(a, f), mul(b, h)));
  intmax_t k = mod(add(mul(c, e), mul(d, g)));
  intmax_t l = mod(add(mul(c, f), mul(d, h)));
  return matrix(i, j, k, l);
}

matrix matpow(matrix const& m, intmax_t n) {
  matrix res(one, zero, zero, one);
  for (matrix dbl = m; n; n >>= one) {
    if (n & one) res = matmul(res, dbl);
    dbl = matmul(dbl, dbl);
  }
  return res;
}

int f(int n) {
  n = sub(n, one);
  matrix m(one, one, one, zero);
  intmax_t a, b;
  std::tie(a, b, std::ignore, std::ignore) = matpow(m, n);
  return mod(add(mul(a, one), mul(b, two)));
}

int main() {
  int T;
  std::cin >> T;

  std::vector<int> a(T);
  for (auto& ai: a) {
    std::cin >> ai;
    std::cout << f(ai) << std::endl;
  }
}
0