test/yukicoder/1097.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://yukicoder.me/problems/no/1097

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1097"
#include <bits/stdc++.h>

#include "library/algebra/group/Add.hpp"
#include "library/datastructure/Doubling.hpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    Doubling<GroupAdd<ll>, 40> db(n);

    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        db.add_arc(i, (i + a) % n, a);
    }

    int q;
    std::cin >> q;
    while (q--) {
        ll k;
        std::cin >> k;
        std::cout << db.calc(0, k).second << "\n";
    }
}

#line 1 "test/yukicoder/1097.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1097"
#include <bits/stdc++.h>

#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "library/datastructure/Doubling.hpp"
template <typename Monoid, int LOG> class Doubling {
    using X = typename Monoid::value_type;
    int n;
    bool is_prepared;

    using P = std::pair<int, X>;
    static constexpr P unit = {-1, Monoid::unit()};
    std::vector<std::vector<P>> DP;

    // a から 2^k 動く
    P k_move(const P &a, int k) {
        if (a.first == -1)
            return a;
        const auto [now, val] = a;
        const auto [nxt, cost] = DP[k][now];
        return {nxt, Monoid::op(val, cost)};
    }

    void build() {
        is_prepared = true;
        for (int k = 0; k < LOG - 1; k++)
            for (int v = 0; v < n; v++)
                DP[k + 1][v] = k_move(DP[k][v], k);
    }

  public:
    Doubling() = default;
    Doubling(int n) : n(n), is_prepared(false) {
        DP.assign(LOG, std::vector<P>(n, unit));
    }

    void add_arc(int from, int to, X x) {
        assert(!is_prepared);
        assert(-1 <= to and to < n);
        DP[0][from] = {to, x};
    }

    // [終点,値] 辺が出てない場所から移動する場合は -1 に着く
    P calc(int s, long long step) {
        assert(step <= (1LL << LOG));
        if (!is_prepared)
            build();

        P res{s, Monoid::unit()};
        for (int k = 0; step; k++, step >>= 1)
            if (step & 1)
                res = k_move(res, k);
        return res;
    }
};
#line 6 "test/yukicoder/1097.test.cpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    Doubling<GroupAdd<ll>, 40> db(n);

    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        db.add_arc(i, (i + a) % n, a);
    }

    int q;
    std::cin >> q;
    while (q--) {
        ll k;
        std::cin >> k;
        std::cout << db.calc(0, k).second << "\n";
    }
}