Dynamic programming like a mathematician

dptable.cc

#include <limits>
#include <array>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#define MO 998244353

template <typename T, size_t rank>
struct Table {
  using SubTable = Table<T, rank-1>;
  std::vector<SubTable> table_;
  template <typename... Args> explicit Table(size_t n, Args... other_ns) : table_(n, Table<T, rank-1>(other_ns...)) {}
  explicit Table(size_t n) : table_(n, Table<T, rank-1>(n)) {}
  template <typename... Args>
  auto& operator()(size_t index, Args... sub_index) {
    return table_[index](sub_index...);
  }
  template <size_t... I>
  auto __call(std::array<size_t, rank> index, std::index_sequence<I...>) {
    return operator()(index[I]...);
  }
  auto& operator()(std::array<size_t, rank>&& index) {
    return __call(index, std::make_index_sequence<rank>{});
  }
};

template <typename T> struct Table<T, 0> {
  T table_;
  explicit Table(size_t) : table_(T()) {}
  T& operator()() {
    return table_;
  }
};

template <typename T, size_t rank>
struct DPTable {
  using SubTable = Table<T, rank-1>;
  Table<T, rank> table_;
  Table<bool, rank> used_;
  template <typename... Args> explicit DPTable(size_t n, Args... other_ns): table_(n, other_ns...), used_(n, other_ns...) {}
  explicit DPTable(size_t n): table_(n), used_(n) {}
  template <typename... Args, typename = std::enable_if_t<sizeof...(Args)==rank>>
  auto get(Args... index) {
    if (used_(index...)) {
      return table_(index...);
    } else {
      table_(index...) = generate({index...});
      used_(index...) = true;
      return table_(index...);
    }
  }
  template <size_t... I>
  auto __call(std::array<size_t, rank> index, std::index_sequence<I...>) {
    return get(index[I]...);
  }
  auto get(std::array<size_t, rank>&& index) {
    return __call(index, std::make_index_sequence<rank>{});
  }
  // HACK: Viriadic functions cannot be virtual
  virtual T generate(std::array<size_t, rank> index) = 0;
};

/*
在二维平面上有一只会移动的机器人。它移动的方式比较特殊，假如它在(x,y)的位置，那么它走一步能到达的位置是(x−1,y−1)、(x−1,y+1)、(x+1,y−1)、(x+1,y+1)。另外，在平面上还有一些不可以触碰的电线，任何时刻机器人都不能落在电线上。我们用若干根直线来描绘这些电线。请问，如果机器人一开始在(0,0)，走t步后恰好到达(x0,y0)有多少种方案？
第一行包含三个由空格隔开的整数x0,y0,t，含义如题所述；第二行包含一个非负整数n，表示用于描绘电线的直线数量；接下来n行，每行两个整数a,b；若a=1，代表有一根电线与直线x=b重合；若a=2，代表有一根电线与直线y=b重合
input:
2 0 2
1
2 1
output:
1
*/
class BotTable : public DPTable<long long, 2> {
 private:
  using super = DPTable<long long, 2>;
  long long t_, xlow_, xhigh_, origin_;
 public:
  explicit BotTable(long long x0, long long t, long long xlow, long long xhigh) : super(2*t+1, t+1), t_(t), xlow_(xlow), xhigh_(xhigh), origin_(t-x0-1) {
  }
  virtual long long generate(std::array<size_t, 2> index) override {
    long long x0 = index[0];
    long long t = index[1];
    assert(x0 >= 0);
    assert(t >= 0);
    if (x0 <= xlow_ || x0 >= xhigh_) {
      return 0;
    } else if (t == 0) {
      return x0 == origin_;
    } else {
	  return (x0 > 0 ? this->get(static_cast<std::size_t>(x0-1), static_cast<std::size_t>(t-1)) % MO : 0) + 
             (x0 < 2*t_-2 ? this->get(static_cast<std::size_t>(x0+1), static_cast<std::size_t>(t-1)) % MO : 0);
    }
  }
};

void make_x_positive(long long& x0, long long& xlow, long long& xhigh) {
  assert(xlow < xhigh);
  if (x0 < 0) {
    x0 = -x0;
    auto tmp = xhigh;
    xhigh = -xlow;
    xlow = -tmp;
  }
  assert(x0 >= 0);
  assert(xlow < 0);
  assert(xhigh > x0);
}

class PalindromeTable : public DPTable<bool, 2>{
 private:
  std::string_view s_;
  using super = DPTable<bool, 2>;
 public:
  explicit PalindromeTable(std::string_view s) : super(s.size()), s_(s) {}
  virtual bool generate(std::array<size_t, 2> index) override {
    size_t i = index[0], j = index[1];
    assert(i >= 0 && i < s_.size());
    assert(j >= 0 && j < s_.size());
    if (i == j) {
      return true;
    } else if (i < j) {
      return this->get({i+1, j-1}) && (s_[i] == s_[j]);
    } else {
      return s_[i] == s_[j];
    }
  }
};

class FibnacciTable : public DPTable<int, 1> {
 public:
  int max_n_;
  explicit FibnacciTable(int n) : DPTable<int, 1>(n), max_n_(n) {}
  virtual int generate(std::array<size_t, 1> index) override {
    size_t i = index[0];
    assert(max_n_ > i);
    switch (i) {
      case 0:
        return 0;
      case 1:
        return 1;
      default:
        return this->get({i-1}) + this->get({i-2});
    }
  }
};

struct Question {
  long long x0;
  long long y0;
  long long t;
  long long xlow = std::numeric_limits<long long>::min();
  long long ylow = std::numeric_limits<long long>::min();
  long long xhigh = std::numeric_limits<long long>::max();
  long long yhigh = std::numeric_limits<long long>::max();
  explicit Question() {
    long long n;
    std::cin >> x0 >> y0 >> t;
    std::cin >> n;
    for (long long i = 0; i < n; ++i) {
      long long a, b;
      std::cin >> a >> b;
      assert(a == 1 || a == 2);
      if (a == 1) {
  	  if (b < 0) {
  	  	xlow = std::max(xlow, b);
  	  } else{
  	  	xhigh = std::min(xhigh, b);
  	  }
      } else {
  	  if (b < 0) {
  	  	ylow = std::max(ylow, b);
  	  } else{
  	  	yhigh = std::min(yhigh, b);
  	  }
      }
    }
  }
};

int huiwen(std::string_view a) {
  PalindromeTable t(a);
  int sum = 0;
  for (int i = 0; i < a.size(); ++i) {
    for (int j = i; j < a.size(); ++j) {
      sum += t.get(i, j);
    }
  }
  return sum;
}

long long botwalk(Question&& q) {
  make_x_positive(q.x0, q.xlow, q.xhigh);
  make_x_positive(q.y0, q.ylow, q.yhigh);
  BotTable xbot(q.x0, q.t, q.xlow+q.t-q.x0-1, std::max(q.xhigh, q.xhigh+q.t-q.x0-1));
  BotTable ybot(q.y0, q.t, q.ylow+q.t-q.y0-1, std::max(q.yhigh, q.yhigh+q.t-q.y0-1));
  auto x = (q.t > 0) ? xbot.get(static_cast<std::size_t>(q.t-1), static_cast<std::size_t>(q.t)) : q.x0 == 0;
  auto y = (q.t > 0) ? ybot.get(static_cast<std::size_t>(q.t-1), static_cast<std::size_t>(q.t)) : q.y0 == 0;
  auto ret = (x * y) % MO;
  return ret < 0 ? ret + MO : ret;
}

int main(int, char** argv) {
  std::string a{"abccbabc"};
  std::cout << huiwen(argv[1]) << std::endl;
  auto t2 = FibnacciTable(18);
  std::cout << t2.get(17) << std::endl;
  std::cout << botwalk(Question()) << std::endl;;
}