#599992 (C++17) No.658 テトラナッチ数列 Hard

提出ソース
結果

問題	No.658 テトラナッチ数列 Hard
ユーザー	r1933
提出日時	2021-01-07 18:31:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	304 ms / 2,000 ms
コード長	20,136 bytes
コンパイル時間	3,339 ms
コンパイル使用メモリ	230,152 KB
実行使用メモリ	26,752 KB
最終ジャッジ日時	2024-11-09 01:03:11
合計ジャッジ時間	5,473 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	32 ms 26,624 KB
testcase_01	AC	31 ms 26,624 KB
testcase_02	AC	32 ms 26,752 KB
testcase_03	AC	33 ms 26,668 KB
testcase_04	AC	127 ms 26,680 KB
testcase_05	AC	143 ms 26,616 KB
testcase_06	AC	173 ms 26,668 KB
testcase_07	AC	182 ms 26,548 KB
testcase_08	AC	210 ms 26,752 KB
testcase_09	AC	301 ms 26,664 KB
testcase_10	AC	304 ms 26,624 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize "Ofast"
#include "bits/stdc++.h"

// Begin Header {{{
#pragma region
using namespace std;
using usize = size_t;
using imax = intmax_t;
using uimax = uintmax_t;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i)
#define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
#define let const auto

constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class Container, class Value = typename Container::value_type,
            enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline istream& operator>>(istream &is, Container &vs) {
    for (auto &v: vs) is >> v;
    return is;
}

inline void output() { cout << "\n"; }
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << " ";
    output(forward<Tail>(tail)...);
}

template <class Container, class Value = typename Container::value_type,
            enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline ostream& operator<<(ostream &os, const Container &vs) {
    static constexpr const char *delim[] = {" ", ""};
    for (auto it = begin(vs); it != end(vs); ++it) {
        os << delim[it == begin(vs)] << *it;
    }
    return os;
}

template <class Iterator>
inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") {
    for (auto it = Begin; it != End; ++it) {
        cout << ((it == Begin) ? "" : delim) << *it;
    }
    cout << last;
}

template <class T>
inline vector<T> makeVector(const T &init_value, size_t sz) {
    return vector<T>(sz, init_value);
}

template <class T, class... Args>
inline auto makeVector(const T &init_value, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(init_value, args...))>(sz, makeVector<T>(init_value, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

template <class Container>
struct reverse_t {
    Container &c;
    reverse_t(Container &c) : c(c) {}
    auto begin() { return c.rbegin(); }
    auto end() { return c.rend(); }
};

template <class Container>
auto reversed(Container &c) {
    return reverse_t<Container>(c);
}

template <class T>
inline bool chmax(T &a, const T &b) noexcept {
    return b > a && (a = b, true);
}

template <class T>
inline bool chmin(T &a, const T &b) noexcept {
    return b < a && (a = b, true);
}

template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}

void operator|=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs | rhs;
}

void ioinit() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    clog << fixed << setprecision(10);
}
#pragma endregion
// }}} End Header

// ModInt {{{
template <intmax_t Modulo>
class ModInt {
public:
    using value_type = intmax_t;

private:
    static constexpr value_type cmod = Modulo; // compile-time
    static value_type rmod; // runtime
    value_type value = 0;

    static constexpr value_type inverse(value_type n, value_type m) {
        value_type a = n;
        value_type b = m;
        value_type x = 0;
        value_type y = 1;
        for (value_type u = y, v = x; a;) {
            const value_type t = b / a;
            swap(x -= t * u, u);
            swap(y -= t * v, v);
            swap(b -= t * a, a);
        }
        if ((x %= m) < 0) x += m;
        return x;
    }

    static value_type normalize(intmax_t n, value_type m) {
        if (n >= m) {
            n %= m;
        } else if (n < 0) {
            if ((n %= m) < 0) n += m;
        }
        return n;
    }

public:
    ModInt() = default;
    ModInt(intmax_t n) : value(normalize(n, getModulo())) {}

    template <typename T>
        constexpr explicit operator T() const { return static_cast<T>(value); }

    ModInt& operator=(intmax_t n) {
        value = normalize(n, getModulo());
        return *this;
    }

    ModInt& operator+=(const ModInt& other) {
        if ((value += other.value) >= getModulo()) value -= getModulo();
        return *this;
    }
    ModInt& operator-=(const ModInt& other) {
        if ((value -= other.value) < 0) value += getModulo();
        return *this;
    }
    ModInt& operator*=(const ModInt& other) {
        value = (value * other.value) % getModulo();
        return *this;
    }
    ModInt& operator/=(const ModInt& other) {
        value = (value * inverse(other.value, getModulo())) % getModulo();
        return *this;
    }

    ModInt& operator++() {
        if (++value == getModulo()) value = 0;
        return *this;
    }
    ModInt& operator--() {
        if (value-- == 0) value = getModulo() - 1;
        return *this;
    }

    ModInt operator++(int) {
        const ModInt tmp(*this);
        ++*this;
        return tmp;
    }
    ModInt operator--(int) {
        const ModInt tmp(*this);
        --*this;
        return tmp;
    }

    friend ModInt operator+(ModInt lhs, const ModInt& rhs) { return lhs += rhs; }
    friend ModInt operator-(ModInt lhs, const ModInt& rhs) { return lhs -= rhs; }
    friend ModInt operator*(ModInt lhs, const ModInt& rhs) { return lhs *= rhs; }
    friend ModInt operator/(ModInt lhs, const ModInt& rhs) { return lhs /= rhs; }

    ModInt operator+() const { return *this; }
    ModInt operator-() const {
        if (value == 0) return *this;
        return ModInt(getModulo() - value);
    }

    friend bool operator==(const ModInt& lhs, const ModInt& rhs) {
        return lhs.value == rhs.value;
    }
    friend bool operator!=(const ModInt& lhs, const ModInt& rhs) {
        return !(lhs == rhs);
    }

    friend ostream& operator<<(ostream& os, const ModInt& n) {
        return os << n.value;
    }
    friend istream& operator>>(istream& is, ModInt& n) {
        is >> n.value;
        n.value = normalize(n.value, getModulo());
        return is;
    }

    static value_type getModulo() { return ((cmod > 0) ? cmod : rmod); }

    template <int M = Modulo, typename T = typename enable_if<(M <= 0)>::type>
        static T setModulo(value_type m) { rmod = m; }
};

template <intmax_t M>
constexpr typename ModInt<M>::value_type ModInt<M>::cmod;
template <intmax_t M>
typename ModInt<M>::value_type ModInt<M>::rmod;
// }}}

// Factorials {{{
template <class ModInt>
class Factorials {
public:
    using value_type = ModInt;

private:
    mutable vector<value_type> m_f, m_i, m_fi;

public:
    Factorials() = default;

    explicit Factorials(intmax_t n) : m_f(n + 1), m_i(n + 1), m_fi(n + 1) {
        m_f[0] = 1;
        for (intmax_t i = 1; i <= n; ++i) {
            m_f[i] = m_f[i - 1] * i;
        }

        const intmax_t MOD = m_f[0].getModulo();
        m_i[1] = 1;
        for (intmax_t i = 2; i <= n; ++i) {
            m_i[i] = -value_type(MOD / i) * m_i[MOD % i];
        }

        m_fi[0] = 1;
        for (intmax_t i = 1; i <= n; ++i) {
            m_fi[i] = m_fi[i - 1] * m_i[i];
        }
    }

    value_type inv(intmax_t n) const { return m_i[n]; }
    value_type fact(intmax_t n) const { return m_f[n]; }
    value_type finv(intmax_t n) const { m_fi[n]; }

    value_type C(intmax_t n, intmax_t k) const {
        if (k < 0 || n < k) return 0;
        return m_f[n] * m_fi[k] * m_fi[n - k];
    }

    value_type P(intmax_t n, intmax_t k) const {
        if (k < 0 || n < k) return 0;
        return m_f[n] * m_fi[n - k];
    }

    value_type H(intmax_t n, intmax_t k) const {
        return C(n + k - 1, k);
    }
};
// }}}

template <class T>
T binomial(intmax_t n, intmax_t k) {
    if (k < 0 || n < k) return 0;
    T ret = 1;
    for (intmax_t i = 1; i <= k; ++i) {
        ret *= n--;
        ret /= i;
    }
    return ret;
}

template <class T>
T power(const T& b, const intmax_t& e) {
    T ret = 1;
    T n = b;
    for (intmax_t p = abs(e); p > 0; p >>= 1) {
        if (p & 1) ret *= n;
        n *= n;
    }
    if (e < 0) return T(1) / ret;
    return ret;
}

template <class T>
T power(const T& b, const string& e) {
    T ret = 1;
    for (const char& c: e) {
        ret = power(ret, 10) * power(b, c - '0');
    }
    return ret;
}

// Edge {{{
template <class Weight>
struct Edge {
    size_t from, to;
    Weight weight;

    Edge() {}
    Edge(size_t from, size_t to, Weight weight = 1) :
        from(from), to(to), weight(weight)
    {}

    bool operator<(const Edge &rhs) const {
        return weight < rhs.weight;
    }

    bool operator>(const Edge &rhs) const {
        return weight > rhs.weight;
    }

    operator size_t() const {
        return to;
    }
};
// }}}

// Graph {{{
template <class Weight>
class Graph : public vector<vector<Edge<Weight>>> {
    using graph = vector<vector<Edge<Weight>>>;

public:
    Graph() {}
    Graph(const size_t V) : graph(V) {}

    void connect(size_t from, size_t to, Weight weight = 1) {
        (*this)[from].emplace_back(from, to, weight);
    }

    friend ostream& operator<<(ostream &strm, const Graph &G) {
        for (size_t v = 0; v < G.size(); ++v) {
            strm << '[' << setw(2) << v << ']';
            for (const auto &e: G[v]) {
                strm << ' ' << setw(2) << e.to;
            }
            strm << '\n';
        }
        return strm;
    }
};
// }}}

// SegmentTree {{{
template <typename Monoid, typename Func>
struct SegmentTree {
    const size_t sz;
    const Func fn;
    const Monoid unity;
    vector<Monoid> seg;

    SegmentTree(const size_t n, const Monoid &u, Func f)
        : sz(1 << (__lg(n + 5) + 1)), fn(f), unity(u), seg(sz * 2, unity) {}

    void set(size_t k, const Monoid &v) {
        seg[k + sz] = v;
    }

    Monoid& operator[](size_t k) {
        return seg[k + sz];
    }

    const Monoid& operator[](size_t k) const {
        return seg[k + sz];
    }

    void build() {
        for (size_t k = sz - 1; k > 0; --k) {
            seg[k] = fn(seg[2 * k], seg[2 * k + 1]);
        }
    }

    void update(size_t k, const Monoid &x) {
        k += sz;
        seg[k] = x;
        while (k >>= 1) {
            seg[k] = fn(seg[2 * k], seg[2 * k + 1]);
        }
    }

    Monoid fold(size_t l, size_t r) const {
        Monoid L = unity;
        Monoid R = unity;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                L = fn(L, seg[l++]);
            }
            if (r & 1) {
                R = fn(seg[--r], R);
            }
        }
        return fn(L, R);
    }
};
// }}}

// BinaryIndexedTree {{{
template <class T>
struct BinaryIndexedTree {
    vector<T> bit;
    const size_t SIZE;

    explicit BinaryIndexedTree(size_t n) : bit(n + 5, 0), SIZE(1 << (__lg(n + 5) + 1)) {}

    void add(int i, const T& v) {
        for (++i; i < bit.size(); i += i & -i) bit[i] += v;
    }

    // [0, i]
    T sum(int i) const {
        T ret = 0;
        for (++i; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    }

    // [s, t]
    T sum(int s, int t) const {
        if (s > t) swap(s, t);
        return sum(t) - sum(s - 1);
    }

    size_t lower_bound(T v) const {
        if (v <= 0) return 0;
        T x = 0;
        for (size_t k = SIZE; k > 0; k >>= 1) {
            if (x + k < bit.size() && bit[x + k] < v) {
                v -= bit[x + k];
                x += k;
            }
        }
        return x;
    }
};
// }}}

// dijkstra {{{
template <class Weight>
vector<Weight> dijkstra(const Graph<Weight> &G, const vector<size_t> &startNodes) {
    using P = pair<Weight, size_t>;
    vector<Weight> dp(G.size(), numeric_limits<Weight>::max());
    priority_queue<P, vector<P>, greater<>> pq;

    for (const auto startNode: startNodes) {
        dp[startNode] = 0;
        pq.emplace(0, startNode);
    }

    while (!pq.empty()) {
        const Weight nowCost = pq.top().first;
        const size_t nowNode = pq.top().second;
        pq.pop();

        if (dp[nowNode] < nowCost) {
            continue;
        }

        for (const auto &e: G[nowNode]) {
            const Weight newCost = dp[nowNode] + e.weight;
            const size_t newNode = e.to;
            if (newCost < dp[newNode]) {
                dp[newNode] = newCost;
                pq.emplace(newCost, newNode);
            }
        }
    }

    return dp;
}
// }}}

// Compress {{{
template <class T>
class Compress {
    vector<T> xs;

public:
    Compress() = default;

    Compress(const vector<T> &vs) {
        add(vs);
    }

    void add(const vector<T> &vs) {
        copy(vs.begin(), vs.end(), back_inserter(xs));
    }

    void add(const T &x) {
        xs.emplace_back(x);
    }

    void build() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
    }

    vector<intmax_t> get(const vector<T> &vs) const {
        vector<intmax_t> ret;
        transform(vs.begin(), vs.end(), back_inserter(ret), [&](const T &v) {
                return distance(xs.begin(), lower_bound(xs.begin(), xs.end(), v));
                });
        return ret;
    }

    unordered_map<T, intmax_t> dict() const {
        unordered_map<T, intmax_t> ret;
        for (intmax_t i = 0; i < xs.size(); ++i) {
            ret[xs[i]] = i;
        }
        return ret;
    }

    const size_t size() const {
        return xs.size();
    }

    const T &operator[](size_t k) const {
        return xs[k];
    }
};
// }}}

const auto sigma = [](auto s, auto t) { return (s + t) * (t - s + 1) / 2; };

// integerOptimizeConvex {{{
template <class Tp, class Fn>
auto integerOptimizeConvex(Tp xl, Tp xu, Fn fn, bool maximize = true) {
    while (xu - xl > 1) {
        const Tp xm = (xl + xu) / 2;
        if (maximize) {
            if (fn(xm - 1) < fn(xm)) xl = xm;
            else xu = xm;
        } else {
            if (fn(xm - 1) > fn(xm)) xl = xm;
            else xu = xm;
        }
    }
    return make_pair(xl, fn(xl));
}
// }}}

vector<bool> sieve(size_t MAX) {
    vector<bool> isPrime(MAX + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (intmax_t i = 2; i * i <= MAX; ++i) {
        if (isPrime[i]) {
            for (intmax_t j = 2; i * j <= MAX; ++j) {
                isPrime[i * j] = false;
            }
        }
    }
    return isPrime;
}

// constexpr intmax_t MOD = intmax_t(1e9) + 7;
// constexpr intmax_t MOD = 998244353;
constexpr intmax_t MOD = 17;
using Mint = ModInt<MOD>;
Factorials<Mint> F(1'000'000);

 // DisjointSet {{{
struct DisjointSet {
    const size_t n;
    mutable vector<int> c;
    explicit DisjointSet(const size_t n) : n(n), c(n, -1) {}

    size_t size(size_t v) const {
        return -c[root(v)];
    }

    size_t root(size_t v) const {
        return (c[v] < 0) ? v : c[v] = root(c[v]);
    }

    bool connected(size_t u, size_t v) const {
        return root(u) == root(v);
    }

    bool unite(size_t u, size_t v) {
        u = root(u);
        v = root(v);
        if (u == v) return false;
        if (-c[u] < -c[v]) swap(u, v);
        c[u] += c[v];
        c[v] = u;
        return true;
    }

    vector<vector<size_t>> groups() {
        vector<size_t> roots(n), group_size(n);
        for (size_t i = 0; i < n; ++i) {
            roots[i] = root(i);
            group_size[roots[i]]++;
        }
        vector<vector<size_t>> res(n);
        for (size_t i = 0; i < n; ++i) {
            res[i].reserve(group_size[i]);
        }
        for (size_t i = 0; i < n; ++i) {
            res[roots[i]].emplace_back(i);
        }
        res.erase(
            remove_if(res.begin(), res.end(),
                        [&](const auto& v) { return v.empty(); }),
            res.end());
        return res;
    }
};
// }}}

template <typename T>
T extgcd(T a, T b, T &x, T &y) {
    T g = a;
    x = 1, y = 0;
    if (b != 0) {
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    return g;
}

  // Matrix {{{
template <class Tp>
class Matrix {
private:
    vector<vector<Tp>> A;

public:
    Matrix() = default;
    Matrix(size_t n, size_t m) : A(n, vector<Tp>(m, 0)) {}
    Matrix(size_t n) : A(n, vector<Tp>(n, 0)) {}
    Matrix(vector<vector<Tp>> A) : A(A) {}

    size_t height() const {
        return A.size();
    }
    size_t width() const {
        return A[0].size();
    }

    vector<Tp>& operator[](size_t k) {
        return A[k];
    }
    const vector<Tp>& operator[](size_t k) const {
        return A[k];
    }

    static Matrix identity(size_t n) {
        Matrix res(n);
        for (size_t i = 0; i < n; ++i) res[i][i] = 1;
        return res;
    }

    Matrix& operator+=(const Matrix& B) {
        const size_t n = height();
        const size_t m = width();
        assert(n == B.height() && m == B.width());
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < m; ++j) {
                A[i][j] += B[i][j];
            }
        }
        return *this;
    }
    Matrix& operator-=(const Matrix& B) {
        const size_t n = height();
        const size_t m = width();
        assert(n == B.height() && m == B.width());
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < m; ++j) {
                A[i][j] -= B[i][j];
            }
        }
        return *this;
    }
    Matrix& operator*=(const Matrix& B) {
        const size_t n = height();
        const size_t m = width();
        const size_t l = B.width();
        assert(m == B.height());
        vector<vector<Tp>> C(n, vector<Tp>(l, 0));
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < m; ++j) {
                for (size_t k = 0; k < l; ++k) {
                    C[i][k] += A[i][j] * B[j][k];
                }
            }
        }
        A.swap(C);
        return *this;
    }
    Matrix operator+(const Matrix& B) const {
        return Matrix(A) += B;
    }
    Matrix operator-(const Matrix& B) const {
        return Matrix(A) -= B;
    }
    Matrix operator*(const Matrix& B) const {
        return Matrix(A) *= B;
    }

    Matrix pow(intmax_t e) const {
        Matrix res = identity(height());
        Matrix B(A);
        while (e > 0) {
            if (e & 1) res *= B;
            B *= B;
            e >>= 1;
        }
        return res;
    }

    Matrix pow(string e) const {
        Matrix res = identity(height());
        Matrix B(A);
        for (const auto c: e) {
            res = res.pow(10) * B.pow(c - '0');
        }
        return res;
    }

    const auto& data() const {
        return A;
    }
};
// }}}

signed main() {
    ioinit();

    var(int, Q);

    Matrix<Mint> A(1, 4);
    A[0][0] = 1;

    Matrix<Mint> B(4, 4);
    B[0][0] = B[1][0] = B[2][0] = B[3][0] = B[0][1] = B[1][2] = B[2][3] = 1;

    while (Q--) {
        var(imax, n);
        if (n <= 4) {
            output(A[0][4 - n]);
        } else {
            Matrix<Mint> res = A * B.pow(n - 4);
            output(res[0][0]);
        }
    }
    return 0;
}
yukicoder

結果

テストケース

ソースコード
