This documentation is automatically generated by online-judge-tools/verification-helper
#include "seq/interpolate_periodic_sequence.hpp"
#pragma once
#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<ll>(n - (len(dat) - 1), p);
n -= k * p;
return dat[n];
}
};
// 差分が 012[345][345][345] みたいなやつ
template <typename T>
struct Interpolate_Difference_Periodic_Sequence {
vc<T> dat;
T d;
int p;
Interpolate_Difference_Periodic_Sequence(vc<T> A) : dat(A) {
vc<T> diff;
FOR(i, len(A) - 1) diff.eb(A[i + 1] - A[i]);
reverse(all(diff));
auto Z = zalgorithm(diff);
Z[0] = 0;
p = max_element(all(Z)) - Z.begin();
ll n = len(A);
d = A[n - 1] - A[n - p - 1];
}
T operator[](ll n) {
if (n < len(dat)) return dat[n];
ll k = ceil<ll>(n - (len(dat) - 1), p);
n -= k * p;
return dat[n] + k * d;
}
};
#line 2 "seq/interpolate_periodic_sequence.hpp"
#line 2 "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 4 "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<ll>(n - (len(dat) - 1), p);
n -= k * p;
return dat[n];
}
};
// 差分が 012[345][345][345] みたいなやつ
template <typename T>
struct Interpolate_Difference_Periodic_Sequence {
vc<T> dat;
T d;
int p;
Interpolate_Difference_Periodic_Sequence(vc<T> A) : dat(A) {
vc<T> diff;
FOR(i, len(A) - 1) diff.eb(A[i + 1] - A[i]);
reverse(all(diff));
auto Z = zalgorithm(diff);
Z[0] = 0;
p = max_element(all(Z)) - Z.begin();
ll n = len(A);
d = A[n - 1] - A[n - p - 1];
}
T operator[](ll n) {
if (n < len(dat)) return dat[n];
ll k = ceil<ll>(n - (len(dat) - 1), p);
n -= k * p;
return dat[n] + k * d;
}
};