seq/interpolate_periodic_sequence.hpp

• View this file on GitHub
• Last update: 2024-09-03 08:13:21+09:00
• Include: #include "seq/interpolate_periodic_sequence.hpp"

Depends on

• string/zalgorithm.hpp

Verified with

• test/3_yukicoder/2858.test.cpp

Code

#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;
  }
};

Back to top page