cp-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub Joe75792433/cp-library

:heavy_check_mark: test/yukicoder/214/214-test-00.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/214
#include <bits/stdc++.h>
#include <atcoder/modint>
#include "cplib/convolution_naive.hpp"
#include "cplib/linear_recurrence.hpp"
#include "cplib/vector_io.hpp"

using namespace std;
using namespace atcoder;
using namespace cplib;

#ifdef DEBUG
template <typename T, typename U> void debug_print(T var_name, U value) {
    cerr << var_name << ": " << value << endl;
}
#define debug(x) debug_print(#x, x)
constexpr bool is_debug = true;
#else
//#pragma GCC target("arch=skylake-avx512")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define debug(x)
constexpr bool is_debug = false;
#endif

using ll = long long;
template <typename T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using vector2 = vector<vector<T>>;
template <typename T> using vector3 = vector<vector2<T>>;
template <typename T> using vector4 = vector<vector3<T>>;
template <typename T> using vector5 = vector<vector4<T>>;
template <typename T> using vector6 = vector<vector5<T>>;
template <typename T>
inline vector2<T> make_vector2(const size_t l0,
                               const size_t l1,
                               const T& init = T()) {
    return vector2<T>(l0, vector<T>(l1, init));
}
template <typename T>
inline vector3<T> make_vector3(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const T& init = T()) {
    return vector3<T>(l0, make_vector2<T>(l1, l2, init));
}
template <typename T>
inline vector4<T> make_vector4(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const T& init = T()) {
    return vector4<T>(l0, make_vector3<T>(l1, l2, l3, init));
}
template <typename T>
inline vector5<T> make_vector5(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const T& init = T()) {
    return vector5<T>(l0, make_vector4<T>(l1, l2, l3, l4, init));
}
template <typename T>
inline vector6<T> make_vector6(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const size_t l5,
                               const T& init = T()) {
    return vector6<T>(l0, make_vector5<T>(l1, l2, l3, l4, l5, init));
}

#define rep(...) overloadrep(__VA_ARGS__, rep4_, rep3_, rep2_)(__VA_ARGS__)
#define overloadrep(_1, _2, _3, _4, repn_, ...) repn_
#define rep2_(i, n) rep4_(i, 0, n, 1)
#define rep3_(i, a, b) rep4_(i, a, b, 1)
#define rep4_(i, a, b, s) for (auto i = (a); i < (b); i += (s))
#define repr(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define foreach(x, a) for (auto& x : (a))

inline void din_() {}
template <class Head, class... Tail>
inline void din_(Head&& head, Tail&&... tail) {
    cin >> head;
    din_(move(tail)...);
}
#define din(T, ...) \
    T __VA_ARGS__;  \
    din_(__VA_ARGS__)

inline void dout() { cout << '\n'; }
template <typename Head, typename... Tail>
inline void dout(const Head& head, const Tail&... tail) {
    cout << head;
    if constexpr (sizeof...(tail) > 0) {
        cout << ' ';
    }
    dout(tail...);
}

template <class T = ll> inline T IN() {
    T x;
    cin >> x;
    return (x);
}

inline void YesNo(bool b, const string yes, const string no) noexcept {
    cout << (b ? yes : no) << '\n';
}
inline void YES(bool b) noexcept { YesNo(b, "YES", "NO"); }
inline void Yes(bool b) noexcept { YesNo(b, "Yes", "No"); }
inline void POSSIBLE(bool b) noexcept { YesNo(b, "POSSIBLE", "IMPOSSIBLE"); }
inline void Possible(bool b) noexcept { YesNo(b, "Possible", "Impossible"); }
inline void FIRST(bool b) noexcept { YesNo(b, "FIRST", "SECOND"); }
inline void First(bool b) noexcept { YesNo(b, "First", "Second"); }

#define all(x) (x).begin(), (x).end()
template <typename T> inline int siz(const T& x) { return int(x.size()); }
template <typename IntLike> constexpr int Pcnt(const IntLike n) {
    return popcount(static_cast<unsigned long long>(n));
}
template <typename IntLike> constexpr ll Bit(const IntLike n) {
    return 1LL << n;
}
template <typename T> inline void uniq(vector<T>& v) {
    auto result = ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmax(T1& a, const T2& b) noexcept {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmin(T1& a, const T2& b) noexcept {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr char enl = '\n';
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr long double eps = 1e-10;
constexpr int INF = 1'010'000'000;                 // 1e9
constexpr ll llINF = 3'010'000'000'000'000'000LL;  // 3e18
constexpr ll MOD = 1'000'000'007LL;
//constexpr ll MOD = 998244353LL;
using mint = static_modint<MOD>;

void Main([[maybe_unused]] int testcase_i) {
    din(ll, n, p, c);
    vector<mint> coef;
    {
        vector<mint> vp, vc;
        {
            vector2<mint> dp = make_vector2<mint>(p + 1, 13 * p + 1);
            dp[0][0] = 1;
            for (int s : {2, 3, 5, 7, 11, 13}) {
                rep(i, 1, p + 1) rep(j, s + 2 * (i - 1), s * i + 1) {
                    dp[i][j] += dp[i - 1][j - s];
                }
            }
            vp = move(dp[p]);
            dp = make_vector2<mint>(c + 1, 12 * c + 1);
            dp[0][0] = 1;
            for (int s : {4, 6, 8, 9, 10, 12}) {
                rep(i, 1, c + 1) rep(j, s + 2 * (i - 1), s * i + 1) {
                    dp[i][j] += dp[i - 1][j - s];
                }
            }
            vc = move(dp[c]);
        }
        coef = convolution_naive(vp, vc) | views::drop(1) |
               ranges::to<vector<mint>>();
    }
    const int max_step = siz(coef);

    vector<mint> sum_coef = coef;
    repr(i, 0, max_step - 1) sum_coef[i] += sum_coef[i + 1];
    vector<mint> init(max_step);
    init[0] = 1;
    rep(i, 1, max_step) {
        init[i] = sum_coef[i];
        rep(j, i) init[i] += init[i - j - 1] * coef[j];
    }

    dout(linear_recurrence(n, init, coef, convolution_naive<mint>).val());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    rep(i, t) Main(i);
}
#line 1 "test/yukicoder/214/214-test-00.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/214
#include <bits/stdc++.h>
#include <atcoder/modint>
#line 2 "cplib/convolution_naive.hpp"

#line 4 "cplib/convolution_naive.hpp"

namespace cplib {

// 畳み込みをする
// 一方が空の配列ならば空の配列を返す
// 計算量は O(|a||b|)
template <typename T>
std::vector<T> convolution_naive(const std::vector<T>& a,
                                 const std::vector<T>& b) {
    const size_t n = a.size(), m = b.size();
    if (n == 0 || m == 0) return std::vector<T>();

    std::vector<T> result(n + m - 1);
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < m; ++j) {
            result[i + j] += a[i] * b[j];
        }
    }
    return result;
}

}  // namespace cplib
#line 2 "cplib/linear_recurrence.hpp"

#line 5 "cplib/linear_recurrence.hpp"
#include <ranges>
#line 2 "cplib/bostan_mori.hpp"

#line 7 "cplib/bostan_mori.hpp"

namespace cplib {

// 有理式 p(x)/q(x) のn次の係数を求める
// deg(p) < deg(q) かつ q[0] != 0 であること
template <typename T>
T bostan_mori(uint64_t n,
              std::vector<T> p,
              std::vector<T> q,
              const auto& convolution_func) {
    while (n > 0) {
        const size_t len_q = q.size();
        std::vector<T> q_ = q;
        for (size_t i = 1; i < len_q; i += 2) {
            q_[i] *= -1;
        }
        p = convolution_func(p, q_) | std::views::drop(n % 2) |
            std::views::stride(2) | std::ranges::to<std::vector<T>>();
        q = convolution_func(q, q_) | std::views::stride(2) |
            std::ranges::to<std::vector<T>>();
        n /= 2;
    }
    assert(p.size() > 0);
    assert(q.size() > 0);
    return p[0] / q[0];
}

}  // namespace cplib
#line 8 "cplib/linear_recurrence.hpp"

namespace cplib {

// d 次の線形回帰数列 a の第 n 項を求める (0-indexed)
// Bostan-Mori 法で O(d*logd*logn) または O(d^2 * logn)
// 入力: a のうち最初の d 項、線形漸化式の 1 <= i <= d 項前の係数 c_{i-1}、
//     畳み込み関数 convolution_func
template <typename T>
T linear_recurrence(const uint64_t n,
                    const std::vector<T>& a,
                    const std::vector<T>& c,
                    const auto& convolution_func) {
    if (n < a.size()) return a[n];

    const size_t d = c.size();
    assert(a.size() >= d);

    std::vector<T> q = {1};
    q.append_range(c |
                   std::views::transform([](const T& coef) { return -coef; }));
    const std::vector<T> p = convolution_func(a, q) | std::views::take(d) |
                             std::ranges::to<std::vector<T>>();
    return bostan_mori(n, p, q, convolution_func);
}

}  // namespace cplib
#line 2 "cplib/vector_io.hpp"

#line 6 "cplib/vector_io.hpp"

namespace cplib {

template <typename T>
inline std::istream& operator>>(std::istream& is, std::vector<T>& v) {
#ifdef DEBUG
    assert(v.size() != 0);
#endif
    for (auto& x : v) is >> x;
    return is;
}

template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    const size_t len = v.size();
    for (size_t i = 0; i < len - 1; ++i) os << v[i] << ' ';
    if (len > 0) os << v[len - 1];
    return os;
}

}  // namespace cplib
#line 7 "test/yukicoder/214/214-test-00.cpp"

using namespace std;
using namespace atcoder;
using namespace cplib;

#ifdef DEBUG
template <typename T, typename U> void debug_print(T var_name, U value) {
    cerr << var_name << ": " << value << endl;
}
#define debug(x) debug_print(#x, x)
constexpr bool is_debug = true;
#else
//#pragma GCC target("arch=skylake-avx512")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define debug(x)
constexpr bool is_debug = false;
#endif

using ll = long long;
template <typename T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using vector2 = vector<vector<T>>;
template <typename T> using vector3 = vector<vector2<T>>;
template <typename T> using vector4 = vector<vector3<T>>;
template <typename T> using vector5 = vector<vector4<T>>;
template <typename T> using vector6 = vector<vector5<T>>;
template <typename T>
inline vector2<T> make_vector2(const size_t l0,
                               const size_t l1,
                               const T& init = T()) {
    return vector2<T>(l0, vector<T>(l1, init));
}
template <typename T>
inline vector3<T> make_vector3(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const T& init = T()) {
    return vector3<T>(l0, make_vector2<T>(l1, l2, init));
}
template <typename T>
inline vector4<T> make_vector4(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const T& init = T()) {
    return vector4<T>(l0, make_vector3<T>(l1, l2, l3, init));
}
template <typename T>
inline vector5<T> make_vector5(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const T& init = T()) {
    return vector5<T>(l0, make_vector4<T>(l1, l2, l3, l4, init));
}
template <typename T>
inline vector6<T> make_vector6(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const size_t l5,
                               const T& init = T()) {
    return vector6<T>(l0, make_vector5<T>(l1, l2, l3, l4, l5, init));
}

#define rep(...) overloadrep(__VA_ARGS__, rep4_, rep3_, rep2_)(__VA_ARGS__)
#define overloadrep(_1, _2, _3, _4, repn_, ...) repn_
#define rep2_(i, n) rep4_(i, 0, n, 1)
#define rep3_(i, a, b) rep4_(i, a, b, 1)
#define rep4_(i, a, b, s) for (auto i = (a); i < (b); i += (s))
#define repr(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define foreach(x, a) for (auto& x : (a))

inline void din_() {}
template <class Head, class... Tail>
inline void din_(Head&& head, Tail&&... tail) {
    cin >> head;
    din_(move(tail)...);
}
#define din(T, ...) \
    T __VA_ARGS__;  \
    din_(__VA_ARGS__)

inline void dout() { cout << '\n'; }
template <typename Head, typename... Tail>
inline void dout(const Head& head, const Tail&... tail) {
    cout << head;
    if constexpr (sizeof...(tail) > 0) {
        cout << ' ';
    }
    dout(tail...);
}

template <class T = ll> inline T IN() {
    T x;
    cin >> x;
    return (x);
}

inline void YesNo(bool b, const string yes, const string no) noexcept {
    cout << (b ? yes : no) << '\n';
}
inline void YES(bool b) noexcept { YesNo(b, "YES", "NO"); }
inline void Yes(bool b) noexcept { YesNo(b, "Yes", "No"); }
inline void POSSIBLE(bool b) noexcept { YesNo(b, "POSSIBLE", "IMPOSSIBLE"); }
inline void Possible(bool b) noexcept { YesNo(b, "Possible", "Impossible"); }
inline void FIRST(bool b) noexcept { YesNo(b, "FIRST", "SECOND"); }
inline void First(bool b) noexcept { YesNo(b, "First", "Second"); }

#define all(x) (x).begin(), (x).end()
template <typename T> inline int siz(const T& x) { return int(x.size()); }
template <typename IntLike> constexpr int Pcnt(const IntLike n) {
    return popcount(static_cast<unsigned long long>(n));
}
template <typename IntLike> constexpr ll Bit(const IntLike n) {
    return 1LL << n;
}
template <typename T> inline void uniq(vector<T>& v) {
    auto result = ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmax(T1& a, const T2& b) noexcept {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmin(T1& a, const T2& b) noexcept {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr char enl = '\n';
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr long double eps = 1e-10;
constexpr int INF = 1'010'000'000;                 // 1e9
constexpr ll llINF = 3'010'000'000'000'000'000LL;  // 3e18
constexpr ll MOD = 1'000'000'007LL;
//constexpr ll MOD = 998244353LL;
using mint = static_modint<MOD>;

void Main([[maybe_unused]] int testcase_i) {
    din(ll, n, p, c);
    vector<mint> coef;
    {
        vector<mint> vp, vc;
        {
            vector2<mint> dp = make_vector2<mint>(p + 1, 13 * p + 1);
            dp[0][0] = 1;
            for (int s : {2, 3, 5, 7, 11, 13}) {
                rep(i, 1, p + 1) rep(j, s + 2 * (i - 1), s * i + 1) {
                    dp[i][j] += dp[i - 1][j - s];
                }
            }
            vp = move(dp[p]);
            dp = make_vector2<mint>(c + 1, 12 * c + 1);
            dp[0][0] = 1;
            for (int s : {4, 6, 8, 9, 10, 12}) {
                rep(i, 1, c + 1) rep(j, s + 2 * (i - 1), s * i + 1) {
                    dp[i][j] += dp[i - 1][j - s];
                }
            }
            vc = move(dp[c]);
        }
        coef = convolution_naive(vp, vc) | views::drop(1) |
               ranges::to<vector<mint>>();
    }
    const int max_step = siz(coef);

    vector<mint> sum_coef = coef;
    repr(i, 0, max_step - 1) sum_coef[i] += sum_coef[i + 1];
    vector<mint> init(max_step);
    init[0] = 1;
    rep(i, 1, max_step) {
        init[i] = sum_coef[i];
        rep(j, i) init[i] += init[i - j - 1] * coef[j];
    }

    dout(linear_recurrence(n, init, coef, convolution_naive<mint>).val());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    rep(i, t) Main(i);
}

Test cases

Env Name Status Elapsed Memory
g++ challenge01.txt :heavy_check_mark: AC 966 ms 0 MB
g++ hehe.txt :heavy_check_mark: AC 906 ms 0 MB
g++ hoho.txt :heavy_check_mark: AC 986 ms 0 MB
Back to top page