Kitamasa algorithm
(Mylib/DynamicProgramming/SpeedupTechnique/kitamasa_algorithm.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

• yukicoder No.214 素数サイコロと合成数サイコロ (3-Medium)
• yukicoder No.658 テトラナッチ数列 Hard
• TDPC T - フィボナッチ

References

• https://misawa.github.io/others/fast_kitamasa_method.html
• https://smijake3.hatenablog.com/entry/2017/01/02/024712
• http://sugarknri.hatenablog.com/entry/2017/11/18/233936
• https://yosupo.hatenablog.com/entry/2015/03/27/025132

Verified with

• test/yukicoder/658/main.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>

namespace haar_lib {
  template <typename T>
  class kitamasa_algorithm {
    int size_;
    std::vector<T> initial_values_, coeff_;

  public:
    kitamasa_algorithm() {}
    kitamasa_algorithm(int size, const std::vector<T> &initial_values, const std::vector<T> &coeff) : size_(size), initial_values_(initial_values), coeff_(coeff) {}

    std::vector<T> inc(const std::vector<T> &a) const {
      std::vector<T> ret(size_);

      for (int i = 0; i < size_; ++i) ret[i] += a[size_ - 1] * coeff_[i];
      for (int i = 1; i < size_; ++i) ret[i] += a[i - 1];

      return ret;
    }

    std::vector<T> dbl(const std::vector<T> &a) const {
      std::vector<T> ret(size_), b(a);

      for (int j = 0; j < size_; ++j) {
        for (int i = 0; i < size_; ++i) {
          ret[i] += a[j] * b[i];
        }

        b = inc(b);
      }

      return ret;
    }

    T eval(const std::vector<T> &v) const {
      T ret = 0;
      for (int i = 0; i < size_; ++i) ret += v[i] * initial_values_[i];
      return ret;
    }

    std::vector<T> get(int64_t index) const {
      std::vector<T> ret(size_);
      ret[0] = 1;

      bool check = false;
      for (int i = 63; i >= 0; --i) {
        if (check) ret = dbl(ret);

        if (index & (1LL << i)) {
          ret   = inc(ret);
          check = true;
        }
      }

      return ret;
    }

    T operator[](int64_t index) const {
      if (index < size_) return initial_values_[index];
      return eval(get(index));
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/DynamicProgramming/SpeedupTechnique/kitamasa_algorithm.cpp"
#include <cstdint>
#include <vector>

namespace haar_lib {
  template <typename T>
  class kitamasa_algorithm {
    int size_;
    std::vector<T> initial_values_, coeff_;

  public:
    kitamasa_algorithm() {}
    kitamasa_algorithm(int size, const std::vector<T> &initial_values, const std::vector<T> &coeff) : size_(size), initial_values_(initial_values), coeff_(coeff) {}

    std::vector<T> inc(const std::vector<T> &a) const {
      std::vector<T> ret(size_);

      for (int i = 0; i < size_; ++i) ret[i] += a[size_ - 1] * coeff_[i];
      for (int i = 1; i < size_; ++i) ret[i] += a[i - 1];

      return ret;
    }

    std::vector<T> dbl(const std::vector<T> &a) const {
      std::vector<T> ret(size_), b(a);

      for (int j = 0; j < size_; ++j) {
        for (int i = 0; i < size_; ++i) {
          ret[i] += a[j] * b[i];
        }

        b = inc(b);
      }

      return ret;
    }

    T eval(const std::vector<T> &v) const {
      T ret = 0;
      for (int i = 0; i < size_; ++i) ret += v[i] * initial_values_[i];
      return ret;
    }

    std::vector<T> get(int64_t index) const {
      std::vector<T> ret(size_);
      ret[0] = 1;

      bool check = false;
      for (int i = 63; i >= 0; --i) {
        if (check) ret = dbl(ret);

        if (index & (1LL << i)) {
          ret   = inc(ret);
          check = true;
        }
      }

      return ret;
    }

    T operator[](int64_t index) const {
      if (index < size_) return initial_values_[index];
      return eval(get(index));
    }
  };
}  // namespace haar_lib

Back to top page