結果
問題 |
No.1136 Four Points Tour
|
ユーザー |
![]() |
提出日時 | 2021-08-11 12:44:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,719 bytes |
コンパイル時間 | 915 ms |
コンパイル使用メモリ | 91,144 KB |
最終ジャッジ日時 | 2025-01-23 17:35:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 41 |
ソースコード
// This C++ code is transpiled using Jikka transpiler v5.2.0.0 https://github.com/kmyk/Jikka // The original Python code: // from typing import * // // // def solve(n: int) -> int: // a = 1 // bcd = 0 // for _ in range(n): // tmp = bcd // bcd = a + bcd * 2 // a = tmp // return a % 1000000007 // // // def main() -> None: // n = int(input()) // ans = solve(n) // print(ans) // // // if __name__ == '__main__': // main() #include <algorithm> #include <array> #include <cassert> #include <cstdint> #include <functional> #include <iostream> #include <numeric> #include <string> #include <tuple> #include <vector> #line 3 "jikka/modulo_matrix.hpp" /** * @file jikka/modulo_matrix.hpp * @author Kimiyuki Onaka * @copyright Apache License 2.0 */ #line 3 "jikka/divmod.hpp" /** * @file jikka/divmod.hpp * @author Kimiyuki Onaka * @copyright Apache License 2.0 */ #include <cassert> #include <cstdint> namespace jikka { inline int64_t floordiv(int64_t n, int64_t d) { assert(d != 0); return n / d - ((n ^ d) < 0 && n % d); } inline int64_t floormod(int64_t n, int64_t d) { assert(d != 0); n %= d; return (n < 0 ? n + d : n); } inline int64_t ceildiv(int64_t n, int64_t d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d); } inline int64_t ceilmod(int64_t n, int64_t d) { assert(d != 0); return n - ceildiv(n, d) * d; } } // namespace jikka #line 3 "jikka/matrix.hpp" /** * @file jikka/matrix.hpp * @author Kimiyuki Onaka * @copyright Apache License 2.0 */ #include <array> namespace jikka { template <typename T, size_t H, size_t W> using matrix = std::array<std::array<T, W>, H>; namespace mat { template <size_t H, size_t W> std::array<int64_t, H> ap(const matrix<int64_t, H, W> &a, const std::array<int64_t, W> &b) { std::array<int64_t, H> c = {}; for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { c[y] += a[y][x] * b[x]; } } return c; } template <size_t N> matrix<int64_t, N, N> zero() { return {}; } template <size_t N> matrix<int64_t, N, N> one() { matrix<int64_t, N, N> a = {}; for (size_t i = 0; i < N; ++i) { a[i][i] = 1; } return a; } template <size_t H, size_t W> matrix<int64_t, H, W> add(const matrix<int64_t, H, W> &a, const matrix<int64_t, H, W> &b) { matrix<int64_t, H, W> c; for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { c[y][x] = a[y][x] + b[y][x]; } } return c; } template <size_t H, size_t N, size_t W> matrix<int64_t, H, W> mul(const matrix<int64_t, H, N> &a, const matrix<int64_t, N, W> &b) { matrix<int64_t, H, W> c = {}; for (size_t y = 0; y < H; ++y) { for (size_t z = 0; z < N; ++z) { for (size_t x = 0; x < W; ++x) { c[y][x] += a[y][z] * b[z][x]; } } } return c; } template <size_t N> matrix<int64_t, N, N> pow(matrix<int64_t, N, N> x, int64_t k) { matrix<int64_t, N, N> y = one<N>(); for (; k; k >>= 1) { if (k & 1) { y = mul(y, x); } x = mul(x, x); } return y; } } // namespace mat } // namespace jikka #line 10 "jikka/modulo_matrix.hpp" #include <array> namespace jikka { namespace modmat { using jikka::floormod; template <size_t N> std::array<int64_t, N> floormod(std::array<int64_t, N> x, int64_t MOD) { for (size_t i = 0; i < N; ++i) { x[i] = floormod(x[i], MOD); } return x; } template <size_t H, size_t W> matrix<int64_t, H, W> floormod(matrix<int64_t, H, W> a, int64_t MOD) { for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { a[y][x] = floormod(a[y][x], MOD); } } return a; } template <size_t H, size_t W> std::array<int64_t, H> ap(const matrix<int64_t, H, W> &a, const std::array<int64_t, W> &b, int64_t MOD) { std::array<int64_t, H> c = {}; for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { c[y] += a[y][x] * b[x] % MOD; } c[y] = floormod(c[y], MOD); } return c; } template <size_t H, size_t W> matrix<int64_t, H, W> add(const matrix<int64_t, H, W> &a, const matrix<int64_t, H, W> &b, int64_t MOD) { matrix<int64_t, H, W> c; for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { c[y][x] = floormod(a[y][x] + b[y][x], MOD); } } return c; } template <size_t H, size_t N, size_t W> matrix<int64_t, H, W> mul(const matrix<int64_t, H, N> &a, const matrix<int64_t, N, W> &b, int64_t MOD) { matrix<int64_t, H, W> c = {}; for (size_t y = 0; y < H; ++y) { for (size_t z = 0; z < N; ++z) { for (size_t x = 0; x < W; ++x) { c[y][x] += a[y][z] * b[z][x] % MOD; } } } for (size_t y = 0; y < H; ++y) { for (size_t x = 0; x < W; ++x) { c[y][x] = floormod(c[y][x], MOD); } } return c; } template <size_t N> matrix<int64_t, N, N> pow(matrix<int64_t, N, N> x, int64_t k, int64_t MOD) { matrix<int64_t, N, N> y = mat::one<N>(); for (; k; k >>= 1) { if (k & 1) { y = mul(y, x, MOD); } x = mul(x, x, MOD); } return y; } } // namespace modmat } // namespace jikka #line 12 "main.cpp" int64_t solve(int64_t n_0) { return jikka::modmat::ap<2, 2>(jikka::modmat::pow<2>(std::array<std::array<int64_t, 2>, 2>{std::array<int64_t, 2>{0, 1}, std::array<int64_t, 2>{1, 2}}, n_0, 1000000007), std::array<int64_t, 2>{1, 0}, 1000000007)[0]; } int main() { int64_t n_1 = -1; std::cin >> n_1; auto ans_2 = solve(n_1); std::cout << ans_2 << ' '; std::cout << '\n' << ' '; }