This documentation is automatically generated by online-judge-tools/verification-helper
#include "seq/interpolate_periodic_sequence.hpp"
#include "string/zalgorithm.hpp"
// 012[345][345][345] みたいなやつ
template <typename T>
struct Interpolate_Periodic_Sequence {
vc<T> dat;
int p;
Interpolate_Periodic_Sequence(vc<T> A) : dat(A) {
reverse(all(A));
auto Z = zalgorithm(A);
Z[0] = 0;
p = max_element(all(Z)) - Z.begin();
}
T operator[](ll n) {
if (n < len(dat)) return dat[n];
ll k = ceil(n - (len(dat) - 1), p);
n -= k * p;
return dat[n];
}
};
#line 1 "string/zalgorithm.hpp"
template <typename STRING> // string, vector どちらでも
vector<int> zalgorithm(const STRING& s) {
int n = int(s.size());
if (n == 0) return {};
vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
#line 2 "seq/interpolate_periodic_sequence.hpp"
// 012[345][345][345] みたいなやつ
template <typename T>
struct Interpolate_Periodic_Sequence {
vc<T> dat;
int p;
Interpolate_Periodic_Sequence(vc<T> A) : dat(A) {
reverse(all(A));
auto Z = zalgorithm(A);
Z[0] = 0;
p = max_element(all(Z)) - Z.begin();
}
T operator[](ll n) {
if (n < len(dat)) return dat[n];
ll k = ceil(n - (len(dat) - 1), p);
n -= k * p;
return dat[n];
}
};